题解：P11274 「Diligent-OI R1 D」DlgtTemplate

zzzz1234567 · 2024-11-10 19:41:32 · 题解

P11274 「Diligent-OI R1 D」DlgtTemplate

一道比较有意思的背包题目，赛时花了点时间才想明白。

Subtask 0

枚举每个格子选或不选，时间复杂度 O(2^n)。

Subtask 2

稍微模拟一下会发现，b_i 总是大于零会导致我们每次添加一个格子的时候都至少会删除前一个格子，相当于我们已选定的格子永远只有一个，枚举即可。

Subtask 3

由于 b_i 总是等于零，每个格子加进去都不会对之前选定的数有任何影响，所以所有 b_i 非零的格子的 a_i 加起来就是答案。

Subtask 4

所谓的 a_i = 1 实际意义是所有格子的贡献都一样，我们只需要找一个不被清除格子最多的方案，除了第一个格子之外，所有 b_i 非零的格子一定会没有贡献（仅当 b_i=1）或者造成负贡献（仅当 b_i>1）。因此我们选第一个格子和所有 b_i 为零的格子即可。

以上做法都是我根据赛时正解的思路口胡的，因此没有代码，也没有 Subtask 1 的 O(n^3) 做法，不便处请谅解，接下来我们讲正解：

Subtask 5 (正解)

通过对上面部分分的思考和我们对样例的进一步观摩，我们会发现以下性质：

最终选定的格子中，可以分成前后两部分，前半部分不对答案作出贡献，仅用于被后半部分格子的 b_i 清除，后半部分清除前半部分后对答案造成贡献。
这前半部分和后半部分是有序的，也就是说我们可以在答案中找一个分界点 i，在 i 之前的格子选择部分加入前半，之后的格子选择部分加入后半。

有了这个性质，我们就可以把本问题分成两个子问题，一个是找出对于每个分界点，前面最多可以找到多少个用来被清除的格子。另一个是找出对于每个分界点后面，清除一定的数可以得到的最大贡献。

前半问题由于选中的格子最终都会用来被删除，相当于这些格子不对答案造成贡献，只需要选最多格子就行，是不是很像 Subtask 4？实际上也确实是这个做法，选择第一个格子和分界点之前所有 b_i 为零的格子，记 c_i 为分界点为 i 时前半部分的最多选中格子的数量。代码如下：

for(int i=2;i<=n;++i){
    c[i]=c[i-1]+(b[i]==0);
}

后半问题就变成了一个经典的背包问题，每个格子价值为 a_i，代价为 b_i，设 dp_{i,j} 为选择 i \sim n 的格子，总共消耗 j 的代价时能得到的最大价值，十分原汁原味的 01 背包，代码如下：

for(int i=n;i;i--){
  for(int j=0;j<=n;++j){
    dp[i][j]=dp[i+1][j];
  }
  for(int j=b[i];j<=n;++j){
    dp[i][j]=max(dp[i+1][j],dp[i+1][j-b[i]]+a[i]);
  }
}

注意这个背包不需要优化空间复杂度，因为计算答案和找方案时要用到，因此也不需要倒序枚举 j。

这时候你会发现还不能完全地解决本题的各种问题，因为题面里有这样一句话：

特殊地，如果该格子之前的已选格子不到 b_i 个，那么该格子以及该格子以后的格子不会被清除为未选格子。

仔细咀嚼这句话，发现这个情况发生意味着当后半部分的一个格子需要的代价大于前半部分此时有的格子时，我们仍然可以强行选入该格子，这需要以下条件：

这个格子一定是后半部分的第一个格子，否则后半部分在他前面选中的格子应当被他清除。这也意味着发生这个情况的格子有且只有一个。
这个格子之后选中的格子一定是 b_i = 0 的格子，因为前半部分已经没有格子能够再被消除。
这个情况发生代表我们前半部分选几个数都无所谓，所以直接不用考虑前半部分选数的数量了。

综合上述条件，设 g_i 为第 i 个数触发该条件能得到的最大收益，代码如下：

g[i]=dp[i+1][0]+a[i];

到这里这道题就差不多了，在所有满足 j\le c_{i-1} 的 dp_{i,j} 和所有 g_i 中找最大值就是答案，答案有 40 分。至于方案，前半部分直接输出就好，后半部分写一个 dfs 找回背包的转移过程。这部分不是重点，看代码就行了，整道题的时间复杂度瓶颈在背包，有 O(n^2) 的复杂度，其他部分都是 O(n) 的。

整体代码如下，在赛时代码的基础上重构了一下增加可读性，写有部分注释，应该够清楚了：

#include<bits/stdc++.h>//zzzz1234567 
using namespace std;
#define int long long//不开long long见祖宗，这导致我赛时白给了两发 
const int N=3e3+5;
int read(){//快读 
    int num=0,typ=1,c=getchar();
    while('0'>c||c>'9'){
        if(c=='-') typ=-1;
        c=getchar(); 
    }while('0'<=c&&c<='9'){
        num=num*10+c-48;
        c=getchar();
    }return num*typ;
}
int n,ans,a[N],b[N],c[N],dp[N][N],g[N],out[N],cnt;
void dfs(int i,int j,int res){//dfs用于找方案 
    if(i==n+1&&j==0) return;//搜索边界 
    if(res==dp[i+1][j]) dfs(i+1,j,res);//这个格子没有造成贡献 
    else{
        out[++cnt]=i;//计入方案 
        if(j==0) dfs(i+1,0,dp[i+1][0]);//g[i]或dp[i][0]造成贡献 
        else dfs(i+1,j-b[i],dp[i+1][j-b[i]]);//dp[i][j]造成贡献 
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
    }
    for(int i=1;i<=n;++i){
        b[i]=read();
    }
    c[1]=1;
    for(int i=2;i<=n;++i){//计算c
        c[i]=c[i-1]+(b[i]==0);
    }
    memset(dp,-0x3f,sizeof dp);//计算dp
    dp[n+1][0]=0;
    for(int i=n;i;i--){ 
        for(int j=0;j<=n;++j){
            dp[i][j]=dp[i+1][j];
        }
        for(int j=b[i];j<=n;++j){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j-b[i]]+a[i]);
        }
        g[i]=dp[i+1][0]+a[i];//顺便处理g 
    }
    int res1=n+1,res2=0;//确定方案起点 
    for(int i=1;i<=n;++i){//找答案 
        for(int j=0;j<=c[i-1];++j){
            if(dp[i][j]>ans){
                ans=dp[i][j];
                res1=i;res2=j;
            }
        }
        if(g[i]>ans){
            ans=g[i];
            res1=i,res2=0;
        }
    }
    dfs(res1,res2,ans);//找方案 
    printf("%lld\n",res2+cnt);//res2为前半部分格子数量，cnt为后半部分格子数量 
    if(res2){//输出前半部分方案 
        printf("1 ");res2--;
    }
    for(int i=2;i<=n&&res2;++i){
        if(b[i]==0){
            printf("%lld ",i);
            res2--;
        }
    }
    for(int i=1;i<=cnt;++i){//输出后半部分方案 
        printf("%lld ",out[i]);
    }putchar('\n');
    printf("%lld\n",ans);//输出答案 
    return 0;
}