【前后缀背包】牛客寒假集训营4 D 清楚姐姐学01背包(Hard Version)

淩亂°似流年 2024-03-26 04:17 68阅读 0赞

[D-清楚姐姐学01背包(Hard Version)\_2023牛客寒假算法基础集训营4 (nowcoder.com)][D-_01_Hard Version_2023_4 _nowcoder.com]

题意：

![a9b4da65e19f56328fce30baa838ecd7.png][]

思路：

这道题的easy version做法是：对于每个物品都去二分需要增加的价值，然后去check增加之后该物品是否为必选

必选的定义是：选了这个物品之后最大价值一定更大

在check函数里对于选的情况做一次背包，不选的情况做一次背包，然后去比较这两种情况的最大价值，如果是必选的就是合法的

这样的复杂度大概是O(nmlogn)，放在hard version一定超时，因此我们去考虑优化

这里复杂度大的原因很大一部分在于每次check的时候都去做一遍O(nm)的背包，因此我们去考虑怎么去check会更快

即，我们如何快速求出没有该物品时的最大价值

考虑预处理前后缀背包

即，先预处理考虑在前缀i个物品中选，体积为j的最大价值 和 预处理考虑在后缀i个物品中选，体积为j的最大价值，那么没有物品 i 的最大价值就是 dp\[i-1\]\[j\]+dp\[i+1\]\[m-j\]

这样复杂度就变成了O(nm+logn)

然后去枚举增加哪个物品的价值，比较增加前和增加后的最大价值，答案就是增加后的最大价值-增加前的最大价值+1

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=5e3+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    int n,m;
    int v[mxn],w[mxn],pre[mxn][mxn],suf[mxn][mxn];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                pre[i][j]=pre[i-1][j];
                if(j>=v[i]) pre[i][j]=max(pre[i][j],pre[i-1][j-v[i]]+w[i]);
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=0;j<=m;j++){
                suf[i][j]=suf[i+1][j];
                if(j>=v[i]) suf[i][j]=max(suf[i][j],suf[i+1][j-v[i]]+w[i]);
            }
        }
        for(int i=1;i<=n;i++){
            int valn=0,valm=0;
            for(int j=0;j<=m;j++){
                valn=max(valn,pre[i-1][j]+suf[i+1][m-j]);
            }
            if(valn<pre[n][m]) cout<<0<<'\n';
            else{
                for(int j=0;j<=m-v[i];j++){
                    valm=max(valm,pre[i-1][j]+suf[i+1][m-v[i]-j]);
                }
                cout<<max(1ll,valn+1-valm-w[i])<<'\n';
            }
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[D-_01_Hard Version_2023_4 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/46812/D
[a9b4da65e19f56328fce30baa838ecd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4ff0742fdf5641538c731df1267d0652.png