题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1226
状压dp。
f[i][s][k]表示原顺序中前i-1个人都吃了饭，当前状态为s（i及i之后的8个点，已吃饭的二进制为1），上一个吃饭的人的相对距离。
因为是对上一个吃饭的人有限制，可以让l从0到7跑一遍，并更新当前可以取到的l的界。
#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<cmath> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define inf int(1e9) #define ll long long #define maxn 1005 #define eps 1e-5 #define mm 2147483648 #define low(x) (x&(-x)) #define f(x,y,z) g[x][y][z+8] using namespace std; int g[maxn][260][20],bin[20],b[maxn],t[maxn]; int T,n,r; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();} return x*f; } int cal(int x,int y){ if (x==0) return 0; return (t[x]^t[y]); } int main(){ // freopen("in.txt","r",stdin); T=read(); bin[0]=1; rep(i,1,8) bin[i]=bin[i-1]*2; while (T--){ n=read(); rep(i,1,n) t[i]=read(),b[i]=read(); rep(i,1,n+1) rep(j,0,255) rep(k,-8,7) f(i,j,k)=inf; f(1,0,-1)=0; rep(i,1,n) rep(j,0,bin[8]-1) rep(k,-8,7) 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)); continue;} int r=inf; rep(l,0,7) if ((bin[l]&j)==0){ if (i+l>r) break; r=min(r,i+l+b[i+l]); f(i,j+bin[l],l)=min(f(i,j+bin[l],l),f(i,j,k)+cal(i+k,i+l)); } } int ans=inf; rep(k,-8,-1) ans=min(ans,f(n+1,0,k)); printf("%d\n",ans); } return 0; }