Luogu P4095 [HEOI2013]Eden 的新背包问题 思维/动规

时间：2024-09-19 09:36:20

当时一直在想前缀和。。。多亏张队提醒。。。

从1到n背次包，保存每一个状态下的价值，就是不要把第一维压掉；再从n到1背一次，同样记住每种状态；

然后询问时相当于是max(前缀+后缀)，当然前缀后缀中间去掉了一个应去掉的商品。

#include<cstdio>

#include<iostream>

#define R register int

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int n,q;

int a[],b[],c[],f[][],h[][];

signed main() {

    n=g();

    for(R i=;i<=n;++i) a[i]=g(),b[i]=g(),c[i]=g();

    for(R i=;i<=n;++i) for(R j=;j>=;--j) {

        f[i][j]=f[i-][j];

        for(R k=;k<=c[i];++k) if(j>=k*a[i]) f[i][j]=max(f[i][j],f[i-][j-k*a[i]]+k*b[i]);

        else break;

    }

    for(R i=n;i>=;--i) for(R j=;j>=;--j) {

        h[i][j]=h[i+][j];

        for(R k=;k<=c[i];++k) if(j>=k*a[i]) h[i][j]=max(h[i][j],h[i+][j-k*a[i]]+k*b[i]);

        else break;

    } q=g();

    for(R i=;i<=q;++i) {

        R k=g(),w=g(); R ans=;

        for(R i=;i<=w;++i) ans=max(ans,f[k][w-i]+h[k+][i]);

        printf("%d\n",ans);

    }

}

2019.04.25

相关文章