题解 P4095 【[HEOI2013]Eden 的新背包问题 】

· · 题解

保证你能懂&&无脑坑点揭示

这题一看显然是个多重背包二进制拆分转成01背包

然而这样只有50pts

暴力就不解释啦，具体看100pts的解释吧

#include<bits/stdc++.h>
using namespace std;
int n,m,c,ji,f[100005];
struct node{
    int s,id;
}w[100000],v[100000];
inline int read(){
    register int x=0;
    register char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int main(){
    cin>>n;
    for(register int i=1;i<=n;++i){
        register int cw=read(),cv=read(),c=read();
        register int now=1;
        while(now<=c){
            w[++ji].s=cw*now,v[ji].s=cv*now;
            w[ji].id=i,v[ji].id=i;
            c-=now,now*=2;
        }
        if(c){
            w[++ji].s=cw*c,v[ji].s=cv*c;
            w[ji].id=i,v[ji].id=i;
        }
    }
    cin>>m;n=ji;
    for(register int l=1;l<=m;++l){
        register int cn=read()+1,V=read();
        for(register int i=1;i<=n;++i){
            if(w[i].id!=cn){
                for(register int j=V;j>=w[i].s;--j){
                    f[j]=max(f[j],f[j-w[i].s]+v[i].s);
                }
            }
        }
        printf("%d\n",f[V]);
        memset(f,0,sizeof(f));
    }
}

100pts:

考虑怎么优化

我们知道背包其实就是把每一种放法都考虑一遍，我们设的状态是f[i][j]表示考虑到第i个总体积为j的最大价值

而我们要求的是不考虑第i种物品时的最大价值

诶 这不就是f[i-1][V]么～～～

不对其实这样后面的物品就没有被考虑到

那怎么办呢

于是我们可以从后往前再DP一次表示从后面往前面考虑的最大价值

把两个背包的结果合并就是所求啦

然而还有一个恶心的地方

由于搬运题目的人的疏忽

1 ≤ q ≤ 3*105

其实是

1 ≤ q ≤ 3*1e5

我在这上面WA了整整10次。。。(所以我才来写题解纪念纪念)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,c,ji;
ll f1[100005][1005],f2[100005][1005];
struct node{
    int id;ll s;
}w[300005],v[300005];
inline int read(){
    register int x=0;
    register char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int main(){
    cin>>n;
    for(register int i=1;i<=n;++i){
        register int cw=read(),cv=read(),c=read();
        register int now=1;
        while(now<=c){//二进制拆分，不懂的可以记住
            w[++ji].s=cw*now,v[ji].s=cv*now;
            w[ji].id=i,v[ji].id=i;
            c-=now,now*=2;
        }
        if(c){
            w[++ji].s=cw*c,v[ji].s=cv*c;
            w[ji].id=i,v[ji].id=i;
        }//拆分结束
    }
    cin>>m;
    n=ji;//更新物品数量
    for(int i=1;i<=n;i++){//正向01背包
        for(int j=0;j<=1000;j++)f1[i][j]=f1[i-1][j];
        for(int j=1000;j>=w[i].s;j--){
            f1[i][j]=max(f1[i][j],f1[i-1][j-w[i].s]+v[i].s);
        }

    }
    for(int i=n;i>=1;i--){//反向01背包
        for(int j=0;j<=1000;j++)f2[i][j]=f2[i+1][j];
        for(int j=1000;j>=w[i].s;j--){
            f2[i][j]=max(f2[i][j],f2[i+1][j-w[i].s]+v[i].s);
        }

    }
    for(int k=1;k<=m;k++){
        int cn=read()+1,V=read();
        ll ans=0;
        int l=0,r=0;//因为同一种物品可能已被拆成多件物品而这种物品都不能被考虑于是我们要找到不包括这种物品的f1和f2
        while(w[l+1].id<cn&&l<n)++l;
        r=l;
        while(w[r+1].id<=cn&&r<n)++r;
        for(int j=0;j<=V;j++){//这是枚举分配给该种物品之前的物品多少空间
            ans=max(ans,f1[l][j]+f2[r+1][V-j]);//不懂的可以拿样例模拟一下，温馨提示：样例可被拆分成9件物品
        }
        printf("%lld\n",ans);
    }
}