[BZOJ1226]学校食堂
- 在我看来,这是一道难度很大的状压DP。其实,对于我来说,DP,往往状态的设计更为困难,优化倒是次要的。因此,经常性的,随便一道DP题,不知难度如何,都能轻松踩我一顿TAT。
- 这道题折磨我将近一天,最终还是在前辈博客的帮助下,理解了算法。我们来讨论一下解法。
- 首先,对于一个人来说,只有他后面的\(B_i\)个人有可能比他先吃完饭。具体谁先吃谁后吃,并不好递推。发现,\(B_i\)是很小的,我们可以把点 \(i\)后面可能会影响答案的7个点的状态压成二进制数;每次处理的时候,当前状态肯定有一段连续的区间,1~i被处理过了;为了计算一个人所消耗的时间,我们还需要记录一下最近一次吃饭的是哪一位。
- 综上,我们定义状态\(f[i][j][k]\)表示到了第 \(i\)个人,前 \(i-1\)个人已经吃完饭,第 \(i\)个人以及后面7个人的吃饭状态为\(j\),最近一次吃饭的人距离\(i\)为\(k\),此时的最小耗费时间。
- 那么转移就比较容易了:
- 此时第\(i\)个人已经吃过饭,那后面的人吃饭顺序就和他没关系了,所以直接推:\(f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k])\)。
-
\(i\)还未吃过饭,枚举一个位置,在保证合法的情况下,尝试更新答案。(注意边界处理)。
Coding
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e3+10; const int inf=0x3f3f3f3f; int t,n,a[N],b[N],f[N][300][20]; int T(int x,int y){return a[x]^a[y];} int main(){ scanf("%d",&t); while(t--){ memset(f,inf,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]); f[1][0][7]=0; for(int i=1;i<=n;++i) for(int j=0;j<(1<<8);++j){ for(int k=0;k<=15;++k){ if(f[i][j][k]==inf) continue; 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; for(int h=0;h<=7;++h){ if(r<i+h) break; if(j&(1<<h)) continue; r=min(r,i+h+b[i+h]); if(i+k-8) f[i][j|(1<<h)][8+h]=min(f[i][j|(1<<h)][8+h],f[i][j][k]+T(i+h,i+k-8)); else f[i][j|(1<<h)][8+h]=min(f[i][j|(1<<h)][8+h],f[i][j][k]); } } } } int ans=inf; for(int i=0;i<=15;++i) ans=min(ans,f[n+1][0][i]); cout<<ans<<endl; } return 0; }