题解
“写过小笼包你就会发现这是一道模板题”
一开始我是这么想的，结果发现这样可能会出现没有头的情况。
并且要找到头是一件非常困难的事。
所以就用普通状压，设$f(i,j,k)$表示前$i-1$个人吃完，$i~i+7$个人吃饭的状态是$j$，上一个吃的人是$i+k$。
就可以愉快的转移了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
typedef long long ll;
int n,d[1005],t[1005],f[1005][257][17];
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int val(int x,int y){
return (x<=0)?0:(t[x]^t[y]);
}
void solve(){
for(int i=1;i<=n+1;i++)
for(int j=0;j<(1<<8);j++)
for(int k=-8;k<=7;k++)
f[i][j][k+offset]=INF;
f[1][0][-1+offset]=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+offset]>=INF)continue;
if(j&1)//自己吃过了
f[i+1][j>>1][k-1+offset]=min(f[i+1][j>>1][k-1+offset],f[i][j][k+offset]);
else{
int r=n+2;
for(int u=1,v=0;v<8;v++,u<<=1){
if((j&u)==0){
if(i+v>r)break;
r=min(r,i+v+d[i+v]);//不能在这之后选人
f[i][j|u][v+offset]=min(f[i][j|u][v+offset],f[i][j][k+offset]+val(i+k,i+v));
}
}
}
}
}
}
}
void init(){
int T=read();
while(T--){
n=read(),d[0]=n+2;
for(int i=1;i<=n;i++)t[i]=read(),d[i]=read();
solve();
int ans=INF;
for(int i=-8;i<=-1;i++)
ans=min(ans,f[n+1][0][i+offset]);
printf("%d\n",ans);
}
}
int main(){
init();
return 0;
}