BZOJ1079 [SCOI2008]着色方案

看上去比较不可做的DP。好像别人写的记搜跑得飞快。

我看我是写最小表示写上瘾了。

压一下状态，有点像今天第二题。算每种值的有多少。然后直接跑。

感觉废状态比较多啊，跑得好慢。另外用memset清空高维数组会比较快。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 17;
const int maxst = 16009;

#define mbit(_a_,_b_) ((_a_)<<((_b_)<<2))
#define gbit(_a_,_b_) (((_a_)>>((_b_)<<2))&0xf)
#define _l (long long int)

int m, c[maxn], n, mt, tots, slst[maxst];
int f[2][7][maxst];

void dfsState(int t, int l, int v) {
	if (l == mt + 1) {
		slst[tots ++] = v | t;
	}
	else {
		for (int i = 0; i <= t; ++ i)
			dfsState(t - i, l + 1, v | mbit(i, l));
	}
}

inline int fState(int x) {
	return lower_bound(slst, slst + tots, x) - slst;
}

inline void incm(int& a, int b) {
	a += b;
	if (a >= mod)
		a -= mod;
}

#define clearFCur() { \
	for (int i = 1; i <= mt; ++ i) \
		for (int j = 0; j < tots; ++ j) \
			f[cur][i][j] = 0; \
}

int dp() {
	int cur(0), prv(1);
	int sb(0);
	for (int i = 0; i <= mt; ++ i)
		sb |= mbit(c[i], i);
	memset(f, 0, sizeof(f));
	for (int i = 1; i <= mt; ++ i)
		if (gbit(sb, i) > 0)
			f[cur][i - 1][fState(sb - mbit(1, i) + mbit(1, i - 1))] = gbit(sb, i);
	for (int ti = 1; ti < n; ++ ti) {
		swap(cur, prv);
//		clearFCur();
		memset(f[cur], 0, sizeof(f[cur]));
		for (int i = 0; i <= mt; ++ i)
			for (int j = 0; j < tots; ++ j)
				if (f[prv][i][j]) {
					int s(slst[j]), c;
					for (int k = 1; k <= mt; ++ k)
						if ((c = gbit(s, k) - (k == i)))
							incm(f[cur][k - 1][fState(s - mbit(1, k) + mbit(1, k - 1))], _l f[prv][i][j] * c % mod);
				}
	}
	return f[cur][0][fState(m)];
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &m);
	memset(c, 0, sizeof(c));
	mt = 0;
	n = 0;
	for (int i = 0; i < m; ++ i) {
		int tmp;
		scanf("%d", &tmp);
		n += tmp;
		++ c[tmp];
		if (tmp > mt)
			mt = tmp;
	}
	tots = 0;
	dfsState(m, 1, 0);
	sort(slst, slst + tots);
	printf("%d\n", dp());
}