P2157 [SDOI2009]学校食堂

状压DP好题

首先我们考虑怎么设计一个不会TLE的状态

$f_{i,j,k}$ 表示我们开头是i,上次选的数是i+j-8,i向后的一些能选的数状态集合是k

转移的时候我们考虑枚举下一个人,然后直接计算贡献即可qwq

即 $a_{new}^a_{lst}$

但是有点问题,就是你会发现这个k集合是动态变化的,就是说我们限制可能由严->选走某个人之后变松

所以我们每次都尽可能的枚举,然后向计算枚举的这个集合的范围是否满足限制,再进入下一步,就可以减少有效状态

这个东西有一点点细节

转移的时候我们计算 $lst$ ,是 $i+j-8$ ,以及 $newlst$
我们如果选择了i号人,会发生一个集体后移的操作,因为可能存在从1开始连续的一段他们都已经买了菜,而为了决策的充分性我们一下都要转移掉

code:



#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 7;
const int inf = 0x3f3f3f3f;
const int MAXS = 130;//2^7=128
int T, a[MAXN], b[MAXN], n, ans, maxs;
int dp[MAXN][MAXS][17], nxt[MAXS];
//第i个人,上一个是j-8,状态为S

//1,7,2^8-1,初始态为0
inline void init() {
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	// maxs = (1 << b[1]) - 1;
	dp[1][0][7] = 0;
	return ;
}

inline void chkmin(int &x, int y) {
	x = y < x ? y : x;
}

inline void solve() {
	for(int i = 1; i <= n; ++i) {
		maxs = (1 << b[i]) - 1;//允许集合,如果为-1就暴毙了
		for(int S = 0; S <= maxs; ++S) {
			int rc = b[i];
			for(int k = 0; k < b[i]; ++k) {
				if(!(S >> k & 1)) {
					rc = min(b[i + k + 1] + k + 1, rc);
				}
			}
			if(S > (1 << rc) - 1)continue;//这个集合不合法
			for(int j = 0; j <= 15; ++j) {//0->-8,15->+7 j-8+i
				if(dp[i][S][j] != inf) {
					// printf("we are in %d %d %d %d\n", i, S, j, dp[i][S][j]);
					for(int k = 0; k < rc; ++k) {//枚举i后面的人
						if(!(S >> k & 1)) {
							int cost = a[j - 8 + i] ^ a[k + i + 1];
							if(j - 8 + i == 0)cost = 0;//第一个转移
							int nS = S ^ (1 << k);
							int lst = k + 9;
							// printf("cost%d nS%d lst%d lstlst%d?\n", cost, nS, lst, j - 8 + i);
							chkmin(dp[i][nS][lst], dp[i][S][j] + cost);
						}
					}
					//i自己拿了,单独转移
					int qwq = min(nxt[S] + i, n + 1);
					int nS = S >> (nxt[S] - 1);
					int lst = 8 - nxt[S];
					int cost = a[i] ^ a[j - 8 + i];
					if(j - 8 + i == 0)cost = 0;//第一个转移
					// printf("ex trans%d %d %d %d\n", qwq, nS, lst, cost);
					chkmin(dp[qwq][nS][lst], dp[i][S][j] + cost);
				}
			}
		}
	}
	ans = inf;
	for(int j = 0; j <= 15; ++j) {
		ans = min(ans, dp[n + 1][0][j]); //qwq
	}
	printf("%d\n", ans);
}

int main() {
	scanf("%d", &T);
	for(int S = 0; S <= (1 << 7) - 1; ++S) {
		int rc = 0;
		for(int k = 0; k <= 7; ++k) {
			if(!(S >> k & 1)) {
				rc = k + 1;
				break;
			}
		}
		nxt[S] = rc;
		// printf("%d %d\n", S, rc);
	}
	while(T-- > 0) {
		init();
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) {
			scanf("%d%d", &a[i], &b[i]);
			if(i + b[i] > n)b[i] = n - i;//没有意义了
		}
		// for(int i = 1; i <= n; ++i) {
		// 	for(int k = 1; k <= b[i]; ++k) {
		// 		if(k + b[i + k] < b[i]) {
		// 			b[i] = k + b[i + k];
		// 		}
		// 	}
		// 	printf("%d %d\n", i, b[i]);
		// }
		solve();
	}
	return 0;
}

比起插头DP就是大巫见小巫吧

夏晓光(loveJY)的博客

CF161C Abracadabra