首页 > 代码库 > 【BZOJ】1079: [SCOI2008]着色方案（dp+特殊的技巧）
【BZOJ】1079: [SCOI2008]着色方案（dp+特殊的技巧）
http://www.lydsy.com/JudgeOnline/problem.php?id=1079
只能想到5^15的做法。。。。。。。。。。。。。。。。。。。。。。。。。。。果然我太弱。
其实应该是没利用好题目的信息，ci<=5！
那么我们可以将颜色所剩余的格子看做一种等价类！
即，设状态f[a,b,c,d,e]表示还剩1个格子的颜色有a种，剩2个格子的颜色有b种...依次类推。那么转移时
f[a,b,c,d,e]=a*f[a-1,b,c,d,e]+b*f[a+1,b-1,c,d,e]+c*f[a,b+1,c-1,d,e]+...+e*f[a,b,c,d+1,e-1]
可是我们发现没有考虑相邻的情况？没事！我们可以加一维！
我们再加一维，表示上一次用的颜色是等价类last，那么这一次计算的时候因为不能相邻，那么这个这一次放last-1的颜色时要少一个，所以是a-1或b-1或....或e-1然后再乘上后边的f。
那么转移就变成了：
f[a,b,c,d,e,last]=(a-(last==2))*f[a-1,b,c,d,e]+(b-(last==3))*f[a+1,b-1,c,d,e]+(c-(last==4))*f[a,b+1,c-1,d,e]+...+(e-(last==6))*f[a,b,c,d+1,e-1]
而last==6无意义，可以去掉。
那么记忆化搜索即可。
真是一道好题！
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const ll MD=1000000007;ll f[17][17][17][17][17][6];ll dp(int a, int b, int c, int d, int e, int last) { if((a|b|c|d|e)==0) return 1; if(f[a][b][c][d][e][last]) return f[a][b][c][d][e][last]; ll ret=0; if(a) ret+=dp(a-1, b, c, d, e, 1)*(a-(last==2)); if(b) ret+=dp(a+1, b-1, c, d, e, 2)*(b-(last==3)); if(c) ret+=dp(a, b+1, c-1, d, e, 3)*(c-(last==4)); if(d) ret+=dp(a, b, c+1, d-1, e, 4)*(d-(last==5)); if(e) ret+=dp(a, b, c, d+1, e-1, 5)*e; return f[a][b][c][d][e][last]=ret%MD;}int a[6];int main() { int n=getint(); for1(i, 1, n) a[getint()]++; printf("%lld\n", dp(a[1], a[2], a[3], a[4], a[5], 0)); return 0;}
Description
有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。
Input
第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。
Output
输出一个整数，即方案总数模1,000,000,007的结果。
Sample Input
1 2 3
Sample Output
HINT
100%的数据满足：1 <= k <= 15, 1 <= ci <= 5
Source
【BZOJ】1079: [SCOI2008]着色方案（dp+特殊的技巧）