题解：P2157 [SDOI2009] 学校食堂

题目传送门

题目大意

有 \(n\) 个学生，每个学生有一个时间 \(t_i\)，所花费的真实时间为 \(t_i\) 异或上前一个吃饭的同学的 \(t_i\)。每个学生有一个忍耐度，最多可以让后面 \(b_i\) 个同学比自己先吃饭。问在不违反忍耐度的条件下，让所有同学吃饭的最小时间。

解题思路

首先，我们发现 \(b_i\) 很小，考虑状压。状态设置比较离奇，\(dp_{i,j,k}\) 表示到第 \(i\) 个同学，后面7个同学，包括自己的吃饭的状态，\(0\) 是还没吃饭，\(1\) 是吃饭了，\(k\) 表示上一个吃饭的人距离 \(i\) 的距离，所以 \(-8\le k\le 7\)。

现在我们考虑转移，首先如果枚举到的 \(j\) 中，\(j\) 的第一位为 \(1\) ，也就是 \(i\) 已经吃过饭了，那就直接向后转移即可，转移式如下：

\[dp_{i+1,\frac{j}{2},k-1}=dp_{i,j,k} \]

这个转移式比较好理解，\(i+1\) 就是下一个同学，\(\frac{j}{2}\) 就是把 \(i\) 的吃饭状态去掉，而前一个吃完饭的人距离 \(i+1\) 的距离就是 \(k-1\)。

如果 \(j\) 的第一位为 \(0\) ，也就是 \(i\) 还没吃饭，那么就要枚举上一个吃饭的人，再进行转移，枚举的过程中要注意，因为每个人的忍耐度不一定相同，所以要判断一下是否满足前面所有人的忍耐度，转移式如下（\(l\) 就是 \(i\) 后面枚举到第几个人）：

\[dp_{i+1,j|(1<<l),l+8}=\min (dp_{i+1,j|(1<<l),l+8},dp_{i,j,k}+t_{i+k-8} \oplus t_{i+l}) \]

转移式借助代码会好理解很多，其中的 \(+8\) 和 \(-8\) 是因为我的 \(k\) 是从 \(0\) 枚举到 \(15\) 的，所以要调整得到真实值。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
ll t[N],b[N],dp[N][258][20],ans;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll T;cin>>T;while(T--){ll n,m;cin>>n;for(int i=1;i<=n;i++)cin>>t[i]>>b[i];memset(dp,0x3f,sizeof(dp));dp[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(k+i-8>n)break;if(k+i-8<0||dp[i][j][k]>1e9)continue;if(j&1){dp[i+1][j>>1][k-1]=min(dp[i+1][j>>1][k-1],dp[i][j][k]);}else{ll lst=1e18;for(int l=0;l<=7&&l+i<=n;l++){if(l>lst)break;if(j&(1<<l))continue;lst=min(lst,b[i+l]+l);dp[i][j|(1<<l)][l+8]=min(dp[i][j|(1<<l)][l+8],dp[i][j][k]+(i+k-8>0)*(t[l+i]^t[i+k-8]));}}}}}ans=1e18;for(int i=0;i<=8;i++)ans=min(ans,dp[n][1][i]);cout<<ans<<"\n";}return 0;
}