洛谷 P2157 [SDOI2009] 学校食堂

题目传送门

前言

第一次见这么新颖的 $dp$，竟然可以从当前枚举的 $i$ 的前面或者后面转移过来，这不就有后效性了吗？

好了开玩笑

其实只要状态设计好，还是没有后效性的。

思路

状态设计

首先 $B_i\le 7$，所以肯定是状压 $dp$，所以一定起码有两维：一维是当前枚举到的 $i$，一维是压缩后的状态 $s$（具体是什么等会说）。
然后他又说 【当前做的菜所用的时间】 还和 【前一个菜的口味】 有关系，所以需要增加一维，表示上一个打到饭的同学是 $j$。
但是这样开的话数组会炸。由于 $B_i\le 7$，所以我们第三位可以用 $j$ 来表示上一个打饭的同学是 $i+j$（$j$ 的范围等会再说）。

现在来看 $d{p}_{i,s,j}$ 的含义：表示 $[1,i-1]$ 的同学 【已经全部打完饭】 ，现在枚举到第 $i$ 个同学， 【他以及他身后 $7$ 个同学】 的打饭状态是 $s$，【目前最后一个打饭的同学】 是 $i+j$，此时所用的最少时间。

$j$ 的取值范围是 $[-8,7]$。右边界的 $7$ 很容易明白，就是同学 $i$ 最多能忍受到的地方。左边界的 $-8$ 是因为：由于上个打饭的同学 【也是 $[1,i-1]$ 同学中最后一个打饭的】，所以第 $i-1$ 个同学打饭时，他最多插到第 $i-1-7=i-8$ 个同学的前面，所以左边界是 $-1$。
为了防止数组越界，在代码实现时只需要给下标加上一个偏移量就好。

状态转移

首先要分类：第 $i$ 个同学已经打过饭了（即 $s\&1==1$），和第 $i$ 个同学还没打饭（即 $s\&1==0$）。

为什么这么分呢？
因为无论做哪道 $dp$ 时，我们所要做的状态转移就是 【把第 $i$ 位的状态转移到第 $i+1$ 位】。
而在这道题中，只有当 $s\&1==1$ 时，它才能往下一位转移（解释在下面）。

1. 当 $s\&1==1$ 时，$d{p}_{i,s,j}$ 可以转移到 $d{p}_{i+1,s>>1,j-1}$。因为 $i$ 的时间花费已经被计算过了，我们要考虑的就是第 $i+1$ 位及以后的学生。而且对于 $i$ 来说，目前最后一个打饭同学是 $i+j$，那么对于 $i+1$ 来说，目前最后一个打饭的同学是 $i+1+j-1==i+j$，二者是等价的，因此可以转移。
   转移方程：
   $$d{p}_{i+1,s>>1,j-1}=min(d{p}_{i+1,s>>1,j-1},d{p}_{i,s,j})$$
2. 当 $s\&1==0$ 时，此时无法再向 $i+1$ 位转移，因为不满足规定的前 $(i+1)-1$ 位同学都打完了饭。但是我们可以转移一下第二维的状态 $s$，我们可以找到一个 $[i,i+7]$ 区间内没打饭的同学，并现在让他打饭来转移。但是需要注意一点，就是转移时看看 【有没有超过某个同学的忍耐范围】，没超过就转移。
   枚举当前状态 $s$ 的二进制位 $k$，若 $s\&(1<<k)==0$，那么就有转移方程：
   $$d{p}_{i,s|(1<<k),k}=min(d{p}_{i,s|(1<<k),k},d{p}_{i,s,j}+(T_{i+j}\oplus T_{i+k}))$$

边界条件

把 $d{p}_{1,0,0}$ 设为 $0$，其他全设为 $INF$。

答案

a n s = m i n { d p n + 1 , 0 , k } , k ∈ [ − 8 , 0 ] ans = min \{dp_{n + 1, 0, k}\}, k \in [-8, 0] ans=min{dpn+1,0,k​},k∈[−8,0]（之所以是 $n+1$，是因为状态设计中第一维 $i$ 是表示 $[1,i-1]$ 中的同学全部打完饭）。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 7;
const int maxs = (1 << 8) + 7;
const int inf  = 0x3f3f3f3f;

int qr() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
	return x * f;
}

int n;
int t[maxn], b[maxn];

// dp[i][s][j] 表示考虑第 i 个人时
// 他以及他后面 7 个人(一共 8 个人) 的吃饭状态为 s
// 最后一个吃饭的人为 i + k 状态下的最少时间, k ∈ [-8, 7]
int dp[maxn][maxs][25];
void sol() {
	memset(dp, inf, sizeof(dp));
	memset(t, 0, sizeof(t));
	memset(b, 0, sizeof(b));
	n = qr();
	for (int i = 1; i <= n; ++i) t[i] = qr(), b[i] = qr();
	
	dp[1][0][-1 + 10] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int s = 0; s < (1 << 8); ++s) {
			for (int j = -8; j <= 7; ++j) {
				if (dp[i][s][j + 10] == inf) continue;
				if (s & 1) dp[i + 1][s >> 1][j - 1 + 10] = min(dp[i + 1][s >> 1][j - 1 + 10], dp[i][s][j + 10]);
				else {
					int r = inf;
					for (int k = 0; k < 8; ++k) if (!(s & (1 << k))){
						if (i + k > r) break;
						r = min(r, i + k + b[i + k]);
						dp[i][s | (1 << k)][k + 10] = 
							min(dp[i][s | (1 << k)][k + 10], dp[i][s][j + 10] + (i + j == 0 ? 0 : (t[i + k] ^ t[i + j])));
					}
				}
			}
		}
	}
	int ans = inf;
	for (int k = -8; k <= -1; ++k)
		ans = min(ans, dp[n + 1][0][k + 10]);
	printf("%d\n", ans);
}
int main() {
	int T = qr();
	while (T--) sol();
	return 0;
}