[HEOI2013] Eden 的新背包问题

Description

多重背包，多次询问，每次询问都将给出新的总价钱，并且会去掉某种物品，再问此时的多重背包的答案，(1 leq n leq 1000)，(1 leq q leq 3 imes 10^5)， (1 leq a_i,b_i,c_i leq 100)，(0 leq d_i < n)，(0 leq e_i leq 1000)

Solution

正反各运行一次多重背包，分别记为 (f[][],g[][])

对于一个询问 (d,e)，答案则为 (max_i (f[d][i]+g[d+2][e-i]))（下标错位）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1005;

int f[N][N],g[N][N],n,q,a[N],b[N],c[N],d,e;

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<N;j++) f[i][j]=f[i-1][j];
        int tmp=c[i];
        for(int k=0;k<=20;k++)
        {
            if(tmp>(1<<k))
            {
                tmp-=1<<k;
                for(int j=N-1;j>=(1<<k)*a[i];j--)
                {
                    f[i][j]=max(f[i][j],f[i][j-(1<<k)*a[i]]+(1<<k)*b[i]);
                }
            }
        }
        for(int j=N-1;j>=tmp*a[i];j--)
        {
            f[i][j]=max(f[i][j],f[i][j-tmp*a[i]]+tmp*b[i]);
        }
    }

    for(int i=n;i>=1;--i)
    {
        for(int j=0;j<N;j++) g[i][j]=g[i+1][j];
        int tmp=c[i];
        for(int k=0;k<=20;k++)
        {
            if(tmp>(1<<k))
            {
                tmp-=1<<k;
                for(int j=N-1;j>=(1<<k)*a[i];j--)
                {
                    g[i][j]=max(g[i][j],g[i][j-(1<<k)*a[i]]+(1<<k)*b[i]);
                }
            }
        }
        for(int j=N-1;j>=tmp*a[i];j--)
        {
            g[i][j]=max(g[i][j],g[i][j-tmp*a[i]]+tmp*b[i]);
        }
    }

    cin>>q;
    while(q--)
    {
        cin>>d>>e;
        int ans=0;
        for(int i=0;i<=e;i++)
        {
            ans=max(ans,f[d][i]+g[d+2][e-i]);
        }
        cout<<ans<<endl;
    }
}