★题目描述
共有N种商品参与促销。每种物品有价格Ci和原价Vi，以及限购数量Ki。
店主会在活动当天宣布有一种商品退出促销，无法购买。
为了获取最大利益，你准备提前计算好Q种情况。
即在给定携带资金Xi，和无法购买第Yi种物品的情况下，最多能够买走原价总和是多少。
特别提醒，商品论件出售，不允许拆分。
★输入格式
第一行包括一个正整数N，表示共有N件商品。
接下来的N行，每行包括三个自然数Ci, Vi, Ki。表示第i件商品的价格、原价和限购数量。
接下来的一行为Q，表示有Q种可能情况。
接下来的Q行，每行包括两个自然数Xi, Yi。 表示携带Xi块钱，无法购买第Yi种商品
★输出格式
输出包括Q行，每行包括一个正整数，表示对应的情况下你能买走的最大原价总和。
★样例输入
3
1 3 1
1 4 1
1 5 1
1
1 2★样例输出
4★提示
注意，商品编号从0开始。
对于60%的数据，N=50，Q=20。
对于100%的数据，1<=N<=800，1<=Q<=50000，1<=Ci，Vi，Ki<=100，0<=Yi<N，0<=Xi<=1000。
/*
该题是一道多重背包问题
因为本题有禁止购买商品
所以设立两个数组
f(i, j) 表示考虑前 i 种商品，花费 j 元能买的最大原件总和。
g(i, j) 表示考虑后 i 种商品，花费 j 元能买的最大原件总和。
对于单次询问 x, y，则把x元拆成两个部分（x1、x2）
前x1元用于买前y-1商品，后x2元用于买后y+1件商品
*/
#include<bits/stdc++.h>
using namespace std;
const int M = 1000; //身上带的最多的钱
int C[800],V[800],K[800];
int F[801][3001], G[801][3001];
int main(){
int N;
scanf("%d",&N);
for(int i=1; i<=N; ++i) scanf("%d%d%d",&C[i], &V[i], &K[i]);
//正序购买商品
memset(F, 0, sizeof(F));
for(int i=1; i<=N; ++i){ //考虑第i个商品
for(int k=0; k<=K[i]; ++k){ //第i个商品考虑买k个
for(int c=k*C[i]; c<=M; ++c){ //买该商品花费的钱
F[i][c] = max(F[i][c], F[i-1][c-k*C[i]]+k*V[i]); //产生的最大收益
}
}
for(int c=1; c<=M; ++c) F[i][c] = max(F[i][c], F[i][c-1]); //更新
}
//反序购买商品
memset(G, 0, sizeof(G));
for(int i=N; i>0; --i){ //考虑第i个商品
for(int k=0; k<=K[i]; ++k){ //第i个商品考虑买k个
for(int c=k*C[i]; c<=M; ++c){ //买该商品花费的钱
G[i][c] = max(G[i][c], G[i+1][c-k*C[i]]+k*V[i]); //产生的最大收益
}
}
for(int c=1; c<=M; ++c) G[i][c] = max(G[i][c], G[i][c-1]); //更新
}
int Q,x,y;
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&x, &y);
++y; //因为商品编号从0开始
int ans=0;
for(int c=0; c<=x; ++c){
ans = max(ans, F[y-1][c]+G[y+1][x-c]); //第y个商品禁买，花费c买前y-1个商品，花费x-c买后y+1个商品
}
printf("%d\n",ans);
}
return 0;
}