Solution
比较好想的dp， 但是坑不少QAQ， 调半天
由于容忍度 $b_i$<= 7, 所以可以考虑将第$i$个人接下来的$b_i$ 个人作为一个维度记录状态。
于是我们定义数组$f[ i ][ S ]$ 表示前$i-1$个人都已经拿到了菜， S表示$i$和接下来$b_i$个人是否拿到了菜。
然后依次枚举$i$ :第$i$个人， $S$ : $i$与接下来$b_i$个人是否拿到菜， $nt$ ： 下一次谁拿菜， $fr$ : 上一次谁拿菜
还需要通过$judge$来判断该状态是否可行， 最后进行$dp$
具体看代码里的$jud$ 和$dp$ 函数
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
using namespace std; const int N = 1e3 + ;
const int base = ;
const int inf = ; int tas[N], bac[N], f[N][][];
int n, T; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} int jud(int now, int S, int nt, int fr) {
if(f[now][S][fr +base] >= inf) return ;
if((S >> nt) & ) return ;
if(!((S >> fr) & ) && fr >= ) return ;
if(now + fr < ) return ;
rep(i, now, now + nt) if(!((S >> (i - now)) & ) && now + nt > i + bac[i]) return ;
return ;
} void dp(int now, int S, int nt, int fr) {
int ntS = S | ( << nt), tmp = inf; //ntS表示给nt拿完菜的状态
if(now + fr) tmp = min(tmp, f[now][S][fr + base] + (tas[now + nt] ^ tas[now + fr]));
else tmp = min(tmp, f[now][S][fr + base] + );
nt += now;
for(; ntS & ; ntS >>= ) {
f[now][ntS][nt - now + base] = min(f[now][ntS][nt - now + base], tmp);
//printf("%d %d %d\n", now, ntS, nt);
now++;
}
f[now][ntS][nt - now + base] = min(f[now][ntS][nt - now + base], tmp);
//printf("%d %d %d\n", now, ntS, nt);
} void work() {
memset(f, , sizeof(f));
n = rd;
rep(i, , n) tas[i] = rd, bac[i] = rd;
f[][][- + base] = ;
rep(i, , n) rep(j, , ( << (bac[i] + )) - ) rep(k, , bac[i]) rep(fr, -, ) {//fr必须从-8枚举
if(!jud(i, j, k, fr)) continue;
dp(i, j, k, fr);
}
int ans = inf;
rep(i, -, ) ans = min(ans, f[n][][i + base]);
printf("%d\n", ans);
} int main()
{
T = rd;
rep(i, , T) work();
}