题目传送门
这道题的思想是$DP$。
首先通过简单推理发现：$(a|b)-(a&b)=ahat{} b$。[$(a and b) - (a or b) = a xor b$]
发现对于第$i$个同学的饭菜的选择受到2方面影响：
是否在前面的某个没有选择的同学$>B_i$的位置；
上一次选择的同学。
观察数据信息可知$B_i leq 7$。
也就是说如果选择了第$i$个，那么最多只能选到第$i+7$个同学。前提是第$i$位同学之前全部选完了。
所以我们用状压写。同时记录上一轮选的同学相对于第$i$位同学的位置，推算得范围一定在$-8sim 7$之间（包含两边）。
设$f[i][S][x]$为第$i$个之前的同学全部选完，$S$为第$i$到$i+7$同学是否选择的状态，$x$同上，
当第$i$位同学已选择，就可以转移到$f[i+1][S>>1][x-1]$；
其他任意情况时，当第$i+bit$位同学可以被选择时（指不超过未选择的$B[i]$到$B[i+bit-1]$的范围），可以转移到$f[i][S | (1 << bit)][bit]$，贡献为$T[i+x]hat{} T[i+bit]$，再取最小值即可。
边界：$f[1][0][-1] = 0$，其余为$INF$。
注意$x>0$和第一轮的异或结果为$0$，特判一下即可。
因为C++下标不能为负，注意下标偏移。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define re register 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i) 7 #define repd(i, a, b) for (re int i = a; i >= b; --i) 8 #define maxx(a, b) a = max(a, b); 9 #define minn(a, b) a = min(a, b); 10 #define LL long long 11 #define inf (1 << 30) 12 13 inline int read() { 14 int w = 0, f = 1; char c = getchar(); 15 while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar(); 16 while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar(); 17 return w * f; 18 } 19 20 const int maxn = 1e3 + 10; 21 22 int C, N, T[maxn], B[maxn]; 23 24 int f[maxn][1 << 8][16]; 25 26 int main() { 27 C = read(); 28 rep(kase, 1, C) { 29 N = read(); 30 rep(i, 1, N) T[i] = read(), B[i] = read(); 31 memset(f, 0x3f, sizeof(f)); 32 f[1][0][7] = 0; 33 rep(i, 1, N) { 34 rep(S, 0, 255) { 35 int p = 7; 36 rep(x, 0, p) { 37 if (!(S & (1 << x))) 38 rep(j, 0, 15) { 39 if (i+j-8 == 0) T[i+j-8] = T[i+x]; 40 else if (i+j-8 < 0) continue; // 这两句if要注意，可能是 0~80pts 的原因 41 minn(f[i][S | (1 << x)][x + 8], f[i][S][j] + (T[i+j-8] ^ T[i+x])); 42 minn(p, B[i+x]+x); 43 } 44 } 45 rep(x, 0, 15) 46 if (S & 1) minn(f[i+1][S >> 1][x-1], f[i][S][x]); 47 } 48 } 49 int ans = inf; 50 rep(i, 0, 8) minn(ans, f[N][1][i]); 51 printf("%d ", ans); 52 } 53 return 0; 54 }