【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种...依次类推，且当前正在放第n-1*a-2*b-3*c-4*d-5*e+1格子。那么转移就是

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
", 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。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

【BZOJ】1079: [SCOI2008]着色方案（dp+特殊的技巧）

Description

Input

Output

Sample Input

Sample Output

HINT

Source