题解 | #[HEOI2013]EDEN的新背包问题#

变形的多重背包,用二进制先把多重背包转化成01背包,然后再根据每次查询,跳过需要去掉的玩偶,然后开始愉快的dp,然后发现超时了.所以我们得换思路,用空间换时间,用前后缀数组来计算每次的查询,这样时间复杂度就降低了.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(){
    int n;
    cin>>n;
    vector<vector<pii>>groups(n);
    //进行二进制处理
    for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        int t=1;
        while(c){
            int g=min(c,t);
            c-=g;
            t*=2;
            groups[i].push_back({a*g,b*g});
        }
    }
    /*定义前后缀数组,可以先储存查询的值,用最大e值定义数组,这样可以减少时间,但我比
    较懒,就直接用最大值定义了      */
    vector<vector<int>>pre(n+1,vector<int>(1005));
    vector<vector<int>>suf(n+1,vector<int>(1005));
    //前缀数组递推
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1];
        for(auto[w,v]:groups[i-1]){
            for(int j=1003;j>=w;j--){
                pre[i][j]=max(pre[i][j],pre[i][j-w]+v);
            }
        }
    }
    //后缀数组递推
    for(int i=n-1;i>=0;i--){
        suf[i]=suf[i+1];
        for(auto[w,v]:groups[i]){
            for(int j=1003;j>=w;j--){
                suf[i][j]=max(suf[i][j],suf[i][j-w]+v);
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int d,e;
        cin>>d>>e;
        int ans=0;
        for(int k=0;k<=e;k++){
            ans=max(ans,pre[d][k]+suf[d+1][e-k]);
        }
        cout<<ans<<endl;
    }
}