这题状压DP太神了。
g[i][j][k]表示前i-1个人都已打到饭，自己和后七个人打饭的情况是j，当前最后一个打饭的与i的关系是k
如果j&1==1说明当前这个人也打了饭，那么可以转移到g[i+1][j>>1][k-1]因为i+1+k-1==i+k
然后我们再枚举当前哪个人要打饭计算状态即可。
学习了hzwer的代码
1 #include<bits/stdc++.h> 2 #define f(a,b,c) (g[a][b][c+8]) 3 using namespace std; 4 int g[1005][256][16],ins[1005],tas[1005],n,T; 5 int calc(int x,int y) 6 { 7 if(!x)return 0; 8 return tas[x]^tas[y]; 9 } 10 int main() 11 { 12 scanf("%d",&T); 13 while(T--) 14 { 15 memset(g,0x3f,sizeof(g)); 16 f(1,0,-1)=0;scanf("%d",&n); 17 for(int i=1;i<=n;++i)scanf("%d%d",&tas[i],&ins[i]); 18 for(int i=1;i<=n;++i) 19 for(int j=0;j<(1<<8);++j) 20 for(int k=-8;k<=7;++k) 21 if(j&1) 22 { 23 f(i+1,j>>1,k-1)=min(f(i+1,j>>1,k-1),f(i,j,k)); 24 } 25 else 26 { 27 int r=1e9; 28 for(int p=0;p<=7;++p) 29 if((j&(1<<p))==0) 30 { 31 if(i+p>r)break; 32 r=min(r,i+p+ins[i+p]); 33 f(i,j|(1<<p),p)=min(f(i,j|(1<<p),p),f(i,j,k)+calc(i+k,i+p)); 34 } 35 } 36 int ans=1e9; 37 for(int k=-8;k<=-1;++k) 38 ans=min(ans,f(n+1,0,k)); 39 printf("%d ",ans); 40 } 41 return 0; 42 }