[luoguP2157] [SDOI2009]学校食堂Dining（状压DP）

传送门

这种鬼畜的状压DP。。。第一次见

看到 0 <= Bi <= 7 就应该想到状态压缩，然而此题实在太鬼畜，想到也没什么乱用

f[i][j][k]表示前i1个人全部吃完，i~i+7的人的吃饭状态为j，最后一个吃饭的人和i距离为k

因为有可能第i个人及以后的人都好没有吃，最后一个吃饭的人是前i1个人中的，考虑Bi的范围，那么 8 <= k <= 7

所以最后一维统一加上8，防止出现负数下标

如果 j&1，那么f[i][j][k]可以直接转移到f[i+1][j>>1][k1]，那么f[i][j][k]也就没用了，因为这两个状态实质上是一个

否则，枚举集合中新的一个元素来更新f[i][j ^ (1<<l)][l]

初始化：f[i][j][k] = INF，f[1][0][1] = 0

最终答案：f[n+1][0][8,0]

#include <cstdio>#include <cstring>#define N 1011#define f(i, j, k) (g[i][j][k + 8])#define min(x, y) ((x) < (y) ? (x) : (y))int T, n, ans;int a[N], b[N], g[N][1 << 8][16];//g[i][j][k]，i表示前i1个人都吃完了，j表示i~i+7是否吃的集合，k表示最后一个人是i+k吃的//k属于[8,7]所以k这一维要统一加上8 inline int calc(int i, int j)int main()}}ans = 1e9;//f[n + 1][0][8,0]for(i = 8; i <= 1; i++) ans = min(ans, f(n + 1, 0, i));printf("%d\n", ans);}return 0;}

上一篇：[luoguP2051] [AHOI2009]中国象棋（DP）

下一篇：[POJ1741]Tree（点分治模板）