f[i][j][k] 分别代表 1-i-1 个人全部打完饭时 i 及其后 7 个人的状态为 j 时最后一个打饭的人为 i+k 的状态下所用的最小时间
当 i 已经打过饭时 即 j&1 那么 f [i] [j>>1] [k+1] =min(~, f[i] [j] [k]);
如果没有那么枚举其后的打饭的人同时注意要保证忍耐度的条件, 所以利用 r 找 i+h+b[i+h] 的最小值, 也就是 i 所能选取的最远边界
如果当前循环的 h 已经超过范围 r 那么结束此次更新答案
否则 f[i] [j|(1<<h)] [h] =min(~ , f[i][j][k] + i+k?(t[i+k]^t[i+h]):0)
最终在 n+1, 处代表前 n 已经打完饭, j=0 代表后面的状态不再选取, k 由 - 8 到 - 1 的全部情况
- #include<bits/stdc++.h>
- #define rep(i,x,y) for(register int i=x;i<=y;i++)
- using namespace std;
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
- while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x*f;}
- const int N=1050;
- const int inf=0x3f3f3f3f;
- int n,t[N],b[N],dp[N][1<<8][20];
- #define f(i,j,k) dp[i][j][k+8]
- inline void sudo(){ n=read();
- rep(i,1,n) t[i]=read(),b[i]=read();
- memset(dp,inf,sizeof dp);
- f(1,0,-1)=0;
- rep(i,1,n)rep(j,0,(1<<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));
- else{
- int r=inf;
- rep(h,0,7)if(!((j>>h)&1)){// 在这个人之前的未打饭的人
- if(i+h>r) break;
- r=min(r,i+h+b[i+h]);
- // 距离 i 的最远距离
- // 判断 i+k 就是判断上一次是否是起点
- f(i,j|(1<<h),h)=min(f(i,j|(1<<h),h),f(i,j,k)+(i+k?(t[i+k]^t[i+h]):0));
- }
- }
- int ans=inf; rep(k,-8,-1)
- ans=min(ans,f(n+1,0,k));
- printf("%d\n",ans);return;}
- int main(){
- int T=read();while(T--) sudo();return 0;}
完结撒花
来源: http://www.bubuko.com/infodetail-2813327.html