这个题的关键处
1 紧跟着他的bi个人 —— 由此得出任意一个状态都可以表示为 有第一个人没吃到饭做分隔的前面
所有人已吃饭，并用1<<8表示之后的（包括他）的八个人的状态
2 信息仍然是上一个 但是根据此信息就可以的出接口数组，就是作为状态转移接口的一维即
——最后一个吃饭的人
据此可得 f(a,b,c) a——前（a-1）个人已吃
b——八人状态
c——上一个人吃饭到i的距离
#include<cstdio> #include<cstring> #define f(a,b,c) g[a][b][c+8] #define inf 0x3f3f3f3f #define Min(a,b) a<b?a:b using namespace std; int g[1005][1<<8][16],t[1005],e[1005],n,full=(1<<8)-1; int main() { freopen("dining.in","r",stdin); freopen("dining.out","w",stdout); int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&e[i]); memset(g,0x3f,sizeof(g)); f(1,0,-1)=0; int lim=n; for(int l=0;l<8;l++) { if(1+l>lim)break; lim=Min(lim,1+l+e[1+l]);//一定不要忘了这里限制初始化，影响很大！！ f(1,1<<l,l)=0; } for(int i=1;i<=n;i++) for(int j=0;j<=full;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 limit=n; for(int l=0;l<8;l++) if(((1<<l)&j)==0) { if(i+l>limit)break; limit=Min(limit,i+l+e[i+l]); f(i,j|(1<<l),l)=Min(f(i,j|(1<<l),l),f(i,j,k)+(t[k+i]^t[i+l])); } } } int ans=inf; for(int i=-8;i<0;i++) ans=Min(ans,f(n+1,0,i)); printf("%d ",ans); } return 0; }