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

的，所以要调整得到真实值。

代码

CPP

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

题解：P2157 [SDOI2009] 学校食堂

文章操作

题目传送门

题目大意

解题思路

代码

相关推荐

评论

题解：P2157 [SDOI2009] 学校食堂