- \(f[i][j][k]\) 表示在第 \(1 \sim i-1\) 个人已经打完饭的情况下,第 \(i\) 个人以及 \(ta\) 后面的 \(7\) 个人是否打饭的状态为 \(j\),上一个打饭的人是第 \(i + k\) 个人
- 因为是十进制转二进制,所以二进制的最后一位是表示的是第 \(i\) 个人的状态
- 且 \(k\) 的取值范围是 \(-8 \le k \le 7\),所以第三维统一加上 \(8\),区间平移。(\(RE\) 的滋味可不好受)
- \((a ~|~ b) - (a ~\&~ b) = a \oplus b\) (具体过程自己推)
- 当第 \(i\) 个人打好饭了(即 \(j ~\&~ 1\) 为真)时,此时的状态就等价于 \(f[i + 1][j >> 1][k - 7]\),因为当第 \(i\) 个人也打好饭时,对于第 \(i+1\) 个人来说,就是他前面的人都打好了饭,而上一个打饭的人还是第 \((i + 1) + (k - 1) = i + k\) 个人,所以 \(f[i][j][k + 8]\) 也就等价于 \(f[i + 1][j >> 1][k + 7]\)
- 进而得到转移方程:
if (j & 1) f[i + 1][j >> 1][k + 7] = min(f[i + 1][j >> 1][k + 7], f[i][j][k]);
- 若第 \(i\) 个人没打好饭,则可以在第 \(i \sim i + 7\) 个人中选一人打饭,此时就有了忍耐度的限制,因此令 \(lim =\) 当前未打饭的所有人的最大忍受范围
- 超出 \(lim\) 的人打饭会引起众怒,不合法
- 可以枚举当前合法却还没打上饭的人,让他们赶紧干饭,我们也好赶紧统计答案,也就是 \(l\) 从 \(0\) 枚举到 \(7\),一旦发现当前点不合法,直接 \(break\)
- 同时也得注意第一道菜是瞬间完成的,进而得到我们第二种情况下的转移方程:
if (i + k == 0) { //(上一道菜做的是空气)
f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8];
} else { //(上一道真做菜了)
f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8] + (t[i + k] ^ t[i + l]));
}
- 自然 \(f[n + 1][0][k] (0 \le k \le 8)\)就是我们答案出现的位置了,为什么是 \(0 \le k \le 8\) 呢,因为最后一个干上饭的人肯定在队中啊
(总不能做菜给幽灵吃吧),所以要保证 \(n + 1 + (k - 8) \le n + 1\),\(k\) 自然而然地就 \(\le 8\) 了
问为什么 \(k \ge 0\) 的,别学了直接退役吧
#include <bits/stdc++.h>
#define MAXN 1100
#define MX 256
using namespace std;
int C, n, t[MAXN], b[MAXN], f[MAXN][MX][20];
int main() {
scanf("%d", &C);
while (C--) {
memset(f, 0x3f, sizeof(f));
f[1][0][7] = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &t[i], &b[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < MX; j++) {
for (int k = -8; k <= 7; k++) {
if (f[i][j][k + 8] == 0x3f3f3f3f) {
continue;
}
if (j & 1) {
f[i + 1][j >> 1][k + 7] = min(f[i + 1][j >> 1][k + 7], f[i][j][k + 8]);
} else {
int lim = 2e9;
for (int l = 0; l <= 7; l++) {
if (!((j >> l) & 1)) {
if (i + l > lim) {
break;
}
lim = min(lim, i + l + b[i + l]);
if (i + k) {
f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8] + (t[i + k] ^ t[i + l]));
} else {
f[i][j | (1 << l)][l + 8] = min(f[i][j | (1 << l)][l + 8], f[i][j][k + 8]);
}
}
}
}
}
}
}
int ans = 2e9;
for (int i = 0; i <= 8; i++) {
ans = min(ans, f[n + 1][0][i]);
}
printf("%d\n", ans);
}
return 0;
}