这题状压DP。
f[i][j][k]表示前i-1吃了，后面几个吃的人的方案为j，最后吃的是第i+k个人。
然后如果j&1>0可以直接转移到f[i+1][(j>>1)][k]
其他还可以转移到f[i][j+(1<<l)][l]
upd：自己没魔重写一次。。。方程和上面的微有差别，但是注意最后吃的和当前的距离可到达maxb*2
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define f(a,b,c) zheshibushikeyixiajibadingyiya[a][b][c+8] using namespace std; const int inf=(1<<30); int a[1100],b[1100]; int zheshibushikeyixiajibadingyiya[1100][310][20];//前i-1吃了，剩下吃的人的方案为j，最后吃的是第i+k个人 int cal(int x,int y) { if(x==0)return 0; return a[x]^a[y]; } int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]), b[i]=min(b[i],n-i); for(int i=1;i<=n+1;i++) for(int j=0;j<=255;j++) for(int k=-8;k<=7;k++) f(i,j,k)=inf; f(1,0,-1)=0; for(int i=1;i<=n;i++) for(int j=0;j<=255;j++) for(int k=-8;k<=7;k++) if(f(i,j,k)<inf) { if((j&1)>0)f(i+1,(j>>1),k-1)=min(f(i+1,(j>>1),k-1),f(i,j,k)); else { int r=inf; for(int l=0;l<=7;l++) { int bl=(1<<l); if((j&bl)==0) { if(l+i>r)break; r=min(r,l+i+b[i+l]); f(i,j+bl,l)=min(f(i,j+bl,l),f(i,j,k)+cal(i+k,i+l)); } } } } int ans=inf; for(int k=-8;k<=-1;k++) ans=min(ans,f(n+1,0,k)); printf("%d ",ans); } return 0; }
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int a[1100],b[1100]; int cost(int x,int y){return x==0?0:(a[x]|a[y])-(a[x]&a[y]);} int f[1100][310][20];//zt前往后高位到低位 int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),b[i]=i+b[i]; int li=(1<<8)-1; memset(f,63,sizeof(f));f[0][li][0]=0; for(int i=0;i<=n;i++) for(int zt=0;zt<=li;zt++) { bool bk=false;//让i+1先吃会不会发火 if(i==n)bk=true; else for(int k=0;k<8;k++) if(i-k>0 && !(zt&(1<<k)) ) if(b[i-k]<i+1){bk=true;break;} //....check.... if(i==3&&zt==249) { int t;t++; } if(!bk) { for(int k=0;k<16;k++) if(f[i][zt][k]!=f[n+3][0][0]) { int tzt=(zt<<1)-(li+1); f[i+1][tzt|1][0]=min(f[i+1][tzt|1][0],f[i][zt][k]+cost(i-k,i+1)); f[i+1][tzt][k+1]=min(f[i+1][tzt][k+1],f[i][zt][k]); } } //............ for(int k=0;k<16;k++) if(f[i][zt][k]!=f[n+3][0][0]) for(int u=0;u<8;u++) if(i-u>0 && !(zt&(1<<u)) ) f[i][zt|(1<<u)][u]=min(f[i][zt|(1<<u)][u],f[i][zt][k]+cost(i-k,i-u)); //............ } int ans=(1<<30); for(int i=0;i<8;i++)ans=min(ans,f[n][li][i]); printf("%d ",ans); } return 0; }