[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;
}

[BZOJ1226]学校食堂

Coding

相关推荐