洛谷P2157/SDOI2009 学校食堂

@Pelom  September 26, 2019

题意


数据范围:$1 \le N \le 1,000,0 \le T_i \le 1,000,0 \le B_i \le 7,1 \le C \le 5$

题解

因为可以将后面的提前,影响了后效性,需要额外保存后$B_i$个人的状态,注意到$0 \le B_i \le 7$,考虑使用状压
用$f[i][j][k]$表示考虑到第$i$个人,状压保存的其后$B_i$个人的状态为$j$(对应位上$0$表示未完成,$1$表示完成了),上一个完成的人离$i$距离$k(k \in [-8,7])$,也可理解为其编号为$i+k$
由于$k$的范围中有负数,需要整体加上一个定值
对于$i$,若完成(即j&1),则其后的顺序是否提前已不会影响$i$,此时可直接后推,更新$i+1$的状态
$$f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k])$$
$j$右移,去掉$i$的状态;$i+1$离$i+k$的距离为$k-1$
若未完成,枚举其后提前完成的人$l$
$$f[i][j|(1<<l)][l]=min(f[i][j|(1<<l)][l],f[i][j][k]+p);$$
其中$l \in [0,7],p$为时间
在枚举的过程中需要注意满足这之前所有同学的容忍度,并保证该同学之前并未完成
最后的答案即为$$min(f[n][1][i]),i \in [0,8]$$

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000+10;
const int INF=0x3f3f3f3f;
int c,n;
int t[N],b[N];
int ans;
int dp[N][1<<8][1<<4];
template <typename T>
inline T Min(T a,T b){
    return a<b?a:b;
}
int main(){
    scanf("%d",&c);
    for(;c--;){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&t[i],&b[i]);
        ans=INF;
        memset(dp,0x3f,sizeof(dp));
        dp[1][0][-1+8]=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<(1<<8);j++)
                for(int k=-8;k<=7;k++){
                    if(dp[i][j][k+8]==INF)
                        continue;
                    if(j&1)
                        dp[i+1][j>>1][k-1+8]=Min(dp[i+1][j>>1][k-1],dp[i][j][k+8]);
                    else{
                        int r=INF;
                        for(int l=0;l<=7;l++){
                            if((j>>l)&1)
                                continue;
                            if(i+l>r)
                                break;
                            r=Min(r,i+l+b[i+l]);
                            int p=i+k?(t[i+k]^t[i+l]):0;
                            dp[i][j|(1<<l)][l+8]=Min(dp[i][j|(1<<l)][l+8],dp[i][j][k+8]+p);
                        }
                            
                    }
                }
        for(int i=-8;i<=0;i++)
            ans=Min(ans,dp[n][1][i+8]);
        printf("%d\n",ans);
    }
    return 0;
}

添加新评论