[SCOI2008]着色方案

DP

题面

有$n$个木块排成一行，从左到右依次编号为$1～n$。你有$k$种颜色的油漆，其
中第$i$种颜色的油漆足够涂$c_i$个木块。所有油漆刚好足够涂满所有木块，即
$c_1+c_2+...+c_k=n$。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

• $50pts\ n\leq5,c_i\leq3$
• $100pts\ n\leq15,c_i\leq5$

解析

$50pts$算法

直接暴力记搜，状态$f[c_1][c_2][c_3][c_4][c_5][las]$表示 在各油漆剩余量如此，上一次涂第$las$种油漆时 有多少种方案。
空间复杂度$O(3^5*5)=O(1215)$开得下，时间复杂度同。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7;
ll dp[20][5][5][5][5][5][5],k,a[20],tot;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll dfs(re int x,re int a1,re int a2,re int a3,re int a4,re int a5,re int las)
{
  re ll sum=0;
  if(!x) return 1;
  if(dp[x][a1][a2][a3][a4][a5][las]) return dp[x][a1][a2][a3][a4][a5][las];
  if(a1&&las!=1) sum+=dfs(x-1,a1-1,a2,a3,a4,a5,1);
  if(a2&&las!=2) sum+=dfs(x-1,a1,a2-1,a3,a4,a5,2);
  if(a3&&las!=3) sum+=dfs(x-1,a1,a2,a3-1,a4,a5,3);
  if(a4&&las!=4) sum+=dfs(x-1,a1,a2,a3,a4-1,a5,4);
  if(a5&&las!=5) sum+=dfs(x-1,a1,a2,a3,a4,a5-1,5);
  sum%=mod;
  return dp[x][a1][a2][a3][a4][a5][las]=sum;
}
int main()
{
  k=gi();
  fp(i,1,k) a[i]=gi(),tot+=a[i];
  printf("%lld\n",dfs(tot,a[1],a[2],a[3],a[4],a[5],0));
  return 0;
}

$100pts$算法

我竟然完全没注意到$c_i\leq5$
可以发现，油漆量相同的油漆，对答案的贡献本质是相同的。
所以状态改成：表示 各油漆剩余量的油漆种数如此，上一次涂第$las$种油漆时 有多少种方案即可。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7;
ll dp[16][16][16][16][16][6],k,tong[20];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll dfs(re int a1,re int a2,re int a3,re int a4,re int a5,re int las)
{
  re ll sum=0;
  if(a1+a2+a3+a4+a5==0) return 1;
  if(dp[a1][a2][a3][a4][a5][las]!=-1) return dp[a1][a2][a3][a4][a5][las];
  if(a1) sum+=(a1-(las==2))*dfs(a1-1,a2,a3,a4,a5,1);//上次涂的油漆油漆量减了1
  if(a2) sum+=(a2-(las==3))*dfs(a1+1,a2-1,a3,a4,a5,2);
  if(a3) sum+=(a3-(las==4))*dfs(a1,a2+1,a3-1,a4,a5,3);
  if(a4) sum+=(a4-(las==5))*dfs(a1,a2,a3+1,a4-1,a5,4);
  if(a5) sum+=a5*dfs(a1,a2,a3,a4+1,a5-1,5);
  sum%=mod;
  return dp[a1][a2][a3][a4][a5][las]=sum;
}
int main()
{
  k=gi();
  fp(i,1,k) tong[gi()]++;
  memset(dp,-1,sizeof(dp));
  printf("%lld\n",dfs(tong[1],tong[2],tong[3],tong[4],tong[5],0));
  return 0;
}