题解：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;
}