洛谷P4095 [HEOI2013]Eden 的新背包问题题解

题目链接：P4095 [HEOI2013]Eden 的新背包问题

题意：

失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 $n$ 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 $m$ 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 $m$，且价值和最大。

众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。

这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

数据范围：

对于 $100\%$ 的数据，保证 $1 \leq n \leq 1000$，$1 \leq q \leq 3\times 10^5$， $1 \leq a_i,b_i,c_i \leq 100$，$0 \leq d_i < n$，$0 \leq e_i \leq 1000$。

$\sum e_i \le 2\times 10^7$ （讨论区补充的）

不难发现，如果不考虑第 $p$ 个物品

最大的价值其实就是 $1\sim p-1$ 和 $p+1 \sim n$ 的最大价值

考虑正反分别跑一遍多重背包，然后对于每个询问暴力合并泛化物品

单调队列优化更快一点，当然二进制拆分也是可以过的。

二进制拆分写法，时间复杂度 $O(m \sum_{i=1}^{n}\log c_i + \sum e_i)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(8e3+15)
#define M (int)(1e3+15)
int n,cnt,Q,f[N][M],g[N][M],w[N],v[N],id[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    for(int i=1; i<=n; i++)
    {
        int w1,v1,c,t=1;
        read(w1);read(v1);read(c);
        while(t<=c)
        {
            ++cnt;id[cnt]=i;
            w[cnt]=t*w1;v[cnt]=t*v1;
            c-=t;t<<=1;
        }
        ++cnt;w[cnt]=c*w1;v[cnt]=c*v1;id[cnt]=i;
    }
    n=cnt;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=1000; j++) // 不要改成 <w[i] ，会越界的哦~ qwq
            f[i][j]=f[i-1][j];
        for(int j=w[i]; j<=1000; j++)
            f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
    }
    for(int i=n; i>=1; i--)
    {
        for(int j=0; j<=1000; j++)
            g[i][j]=g[i+1][j];
        for(int j=w[i]; j<=1000; j++)
            g[i][j]=max(g[i+1][j],g[i+1][j-w[i]]+v[i]);
    }
    read(Q);
    while(Q--)
    {
        int p,m,res=0,l=0,r=0;
        read(p);read(m);++p;
        while(l+1<=n&&id[l+1]<p)++l;
        r=l;
        while(r+1<=n&&id[r+1]<=p)++r;
        r++;
        for(int k=0; k<=m; k++)
            res=max(res,f[l][k]+g[r][m-k]);
        write(res);pc('\n');
    }
    return 0;
}

单调队列优化写法，时间复杂度 $O(nm+\sum e_i)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e3+15)
#define M (int)(1e3+15)
int n,Q,st,en,t[N],q[N],f[N][M],g[N][M],W[N],V[N],C[N],id[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    for(int i=1; i<=n; i++)
        read(W[i]),read(V[i]),read(C[i]);
    for(int i=1; i<=n; i++)
    {
        int &w=W[i],&v=V[i],&c=C[i];
        c=min(c,1000/w);
        for(int j=1; j<=1000; j++)
            f[i][j]=f[i-1][j];
        for(int d=0; d<w; d++)
        {
            st=en=1;
            for(int k=0; k*w+d<=1000; k++)
            {
                int j=k*w+d;
                while(st<en&&q[en]<=f[i][j]-k*v)--en;
                t[++en]=k;q[en]=f[i][j]-k*v;
                while(st<en&&k-t[st+1]>c)++st;
                f[i][j]=max(f[i][j],q[st+1]+k*v);
            }
        }
    }
    for(int i=n; i>=1; i--)
    {
        int &w=W[i],&v=V[i],&c=C[i];
        c=min(c,1000/w);
        for(int j=1; j<=1000; j++)
            g[i][j]=g[i+1][j];
        for(int d=0; d<w; d++)
        {
            st=en=1;
            for(int k=0; k*w+d<=1000; k++)
            {
                int j=k*w+d;
                while(st<en&&q[en]<=g[i][j]-k*v)--en;
                t[++en]=k;q[en]=g[i][j]-k*v;
                while(st<en&&k-t[st+1]>c)++st;
                g[i][j]=max(g[i][j],q[st+1]+k*v);
            }
        }
    }
    read(Q);
    while(Q--)
    {
        int p,m,res=0,l=0,r=0;
        read(p);read(m);++p;
        for(int k=0; k<=m; k++)
            res=max(res,f[p-1][k]+g[p+1][m-k]);
        write(res);pc('\n');
    }
    return 0;
}