本文主要是介绍bzoj1226 学校食堂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
学校食堂
题目背景：
bzoj1226
分析：状压DP
知道吗，要仔细读题，b[i] <= 7 ······
一开始并没有认真读题，然后没有看到b[i] <= 7导致一直在想这个怎么做的了······然后看到这个就有点思路了，定义f[i][j][k]表示，已经处理完了前i - 1个人，i ~ i + 7个人的用餐情况为j，上一个用餐的人是第i + k个人，因为b[i]的限制，那么可以知道k最多为-8 ~ 7开个16的数组每次加8好了······至于转移呢就是
f[i][j][k] à f[i + 1][j >> 1][k - 1] (j & 1)
f[i][j][k] à f[i + 1][j | (1 << l)][l] + (a[i + k] ^ a[i + l]) (otherwise)
注意在转移过程中的b[i]限制不能被超过，还有就是关于边界的情况，第一个转移有一个k - 1会不会导致出现-9呢，答案是不会的，因为i已经被选择了，那么i - 8一定在i之前被选择，否则状态将不合法，所以转移到i + 1时，不会出现-9（但是如果你之前的状态就挂了······那就GG了）
错误：j | (1 <<l) 写成 j & (1 << l)的一定只有我······
Source：
/*created by scarlyw
*/
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>const int MAXN = 1000 + 10;
const int MAXX = 8;
const int INF = 1000000000;int n, t;
int f[MAXN][1 << MAXX | 1][MAXX << 1];
int a[MAXN], b[MAXN];inline void read_in() {scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]);
}inline void solve() {memset(f, 60, sizeof(f));f[1][0][7] = 0;for (int i = 1; i <= n; ++i) {for (int j = 0; j < (1 << MAXX); ++j) {for (int k = -8; k <= 7; ++k) {if (j & 1) f[i + 1][j >> 1][k - 1 + 8] = std::min(f[i][j][k + 8], f[i + 1][j >> 1][k - 1 + 8]);else {int limit = INF;for (int l = 0; l <= 7; ++l) {if (j & (1 << l)) continue ;if (i + l > limit) break ;limit = std::min(limit, i + l + b[i + l]);f[i][j | (1 << l)][l + 8] = std::min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8] + ((i + k == 0) ? 0 :(a[i + k] ^ a[i + l])));}}}}}int ans = INF;for (int i = 0; i < MAXX * 2; ++i) ans = std::min(f[n + 1][0][i], ans);printf("%d\n", ans);
}int main() {scanf("%d", &t);while (t--) read_in(), solve();return 0;
}这篇关于bzoj1226 学校食堂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
