题目

解法

C++

#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){  for(int k=0; k<=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){  for(int k=0; k<=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;   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;
}