NC20007. [HEOI2013]EDEN的新背包问题
描述
“ 寄 没 有 地 址 的 信 ，这 样 的 情 绪 有 种 距 离 ，你 放 着 谁 的 歌 曲 ，是 怎 样 的 心 情 。 能 不 能 说 给 我 听 。”
失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的 感觉，却不能回忆起她的音容笑貌。
记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市 中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的 一个问题：有 n 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有 限次，在携带的价钱 m 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多 少个，才能使得选择的玩偶总价钱不超过 m，且价值和最大。
众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似 乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被 选择），再问此时的多重背包的答案（即前一段所叙述的问题）。
这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？
输入描述
第一行一个数n，表示有n个玩偶，玩偶从0开始编号第二行开始后面的 n行，每行三个数 ai, bi, ci，分别表示买一个第i个玩偶需要的价钱，获得的价值以及第i个玩偶的限购次数。接下来的一行为q，表示询问次数。接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）
输出描述
输出q行，第i行输出对于第 i个询问的答案。
示例1
输入:
5 2 3 4 1 2 1 4 1 2 2 1 1 3 2 3 5 1 10 2 7 3 4 4 8 0 5
输出:
13 11 6 12 4
C++(g++ 7.5.0) 解法, 执行用时: 97ms, 内存消耗: 7900K, 提交时间: 2022-08-09 23:14:14
#include<iostream>
using namespace std;
const int N=1005;
int n;
int a[N],b[N],c[N];
int f1[N][N],f2[N][N];
int main(){
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<=1000;++j)
for(int k=0;k<=c[i]&&j>=k*a[i];++k)
f1[i][j]=max(f1[i][j],f1[i-1][j-k*a[i]]+k*b[i]);
for(int i=n;i>=1;--i)
for(int j=0;j<=1000;++j)
for(int k=0;k<=c[i]&&j>=k*a[i];++k)
f2[i][j]=max(f2[i][j],f2[i+1][j-k*a[i]]+k*b[i]);
int q,x,y,ans=0;
cin>>q;
for(int i=0;i<q;++i){
cin>>x>>y;
++x,ans=0;
for(int j=0;j<=y;++j)
ans=max(ans,f1[x-1][j]+f2[x+1][y-j]);
printf("%d\n",ans);
}
}