传送门
裸的状压dp
f[i][j][k]表示前i个人，i和他之前7个人是否打完菜，上一个打菜的人是k的最小时间。
然后就是愉快的dp了。
枚举当前谁打菜就可以了。
#include<cstring>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define get getchar()
#define f(i,j,k) g[i][j][k+8]
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){
ll x=0,f=1;
char ch=get;
for (;ch<'0'||ch>'9';ch=get) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=get) x=x*10+ch-48;
return x*f;
}
int g[1005][257][17],a[1005],b[1005];
int cas,n,ans,lim;
int ppp(int x,int y){return x==0?0:a[x]^a[y];}
int main(){
cas=read();
while (cas--){
n=read();
for (int i=1;i<=n;i++) a[i]=read(),b[i]=read();
memset(g,inf,sizeof(g));
f(1,0,-1)=0;
for (int i=1;i<=n;i++)
for (int j=0;j<1<<8;j++)
for (int k=-8;k<=7;k++)
if (f(i,j,k)<inf){
if (j&1) f(i+1,j>>1,k-1)=min(f(i+1,j>>1,k-1),f(i,j,k));
else{
int lim=inf;
for (int l=0;l<=7;l++)
if (!(j&(1<<l))){
if (i+l>lim) break;
lim=min(lim,i+l+b[i+l]);
f(i,j+(1<<l),l)=min(f(i,j+(1<<l),l),f(i,j,k)+ppp(i+k,i+l));
}
}
}
ans=inf;
for (int i=-8;i<=7;i++) ans=min(ans,f(n+1,0,i));
printf("%d\n",ans);
}
}