题意
略
数据范围：$1 \le N \le 1,000，0 \le T_i \le 1,000，0 \le B_i \le 7，1 \le C \le 5$
题解
因为可以将后面的提前，影响了后效性，需要额外保存后$B_i$个人的状态，注意到$0 \le B_i \le 7$，考虑使用状压
用$f[i][j][k]$表示考虑到第$i$个人，状压保存的其后$B_i$个人的状态为$j$（对应位上$0$表示未完成，$1$表示完成了），上一个完成的人离$i$距离$k(k \in [-8,7])$，也可理解为其编号为$i+k$
由于$k$的范围中有负数，需要整体加上一个定值
对于$i$，若完成（即j&1），则其后的顺序是否提前已不会影响$i$，此时可直接后推，更新$i+1$的状态
$$f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k])$$
$j$右移，去掉$i$的状态；$i+1$离$i+k$的距离为$k-1$
若未完成，枚举其后提前完成的人$l$
$$f[i][j|(1<<l)][l]=min(f[i][j|(1<<l)][l],f[i][j][k]+p);$$
其中$l \in [0,7],p$为时间
在枚举的过程中需要注意满足这之前所有同学的容忍度，并保证该同学之前并未完成
最后的答案即为$$min(f[n][1][i]),i \in [0,8]$$
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000+10;
const int INF=0x3f3f3f3f;
int c,n;
int t[N],b[N];
int ans;
int dp[N][1<<8][1<<4];
template <typename T>
inline T Min(T a,T b){
return a<b?a:b;
}
int main(){
scanf("%d",&c);
for(;c--;){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&t[i],&b[i]);
ans=INF;
memset(dp,0x3f,sizeof(dp));
dp[1][0][-1+8]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<8);j++)
for(int k=-8;k<=7;k++){
if(dp[i][j][k+8]==INF)
continue;
if(j&1)
dp[i+1][j>>1][k-1+8]=Min(dp[i+1][j>>1][k-1],dp[i][j][k+8]);
else{
int r=INF;
for(int l=0;l<=7;l++){
if((j>>l)&1)
continue;
if(i+l>r)
break;
r=Min(r,i+l+b[i+l]);
int p=i+k?(t[i+k]^t[i+l]):0;
dp[i][j|(1<<l)][l+8]=Min(dp[i][j|(1<<l)][l+8],dp[i][j][k+8]+p);
}
}
}
for(int i=-8;i<=0;i++)
ans=Min(ans,dp[n][1][i+8]);
printf("%d\n",ans);
}
return 0;
}