dp双向预处理+分段查询+合并
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 1010 int n,q; struct toy{ int v,w,s; }toys[N]; int f[N][100010]; int g[N][100010]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>toys[i].v>>toys[i].w>>toys[i].s; } for (int i = 1; i <= n; i++) for (int j = 0; j <= 1000; j++) for (int k = 0; k <= toys[i].s; k++) { if (k * toys[i].v <= j) f[i][j] = max(f[i][j], f[i - 1][j - toys[i].v * k] + toys[i].w * k); else break; } for (int i = n; i; i--) for (int j = 0; j <= 1000; j++) for (int k = 0; k <= toys[i].s; k++) { if (k * toys[i].v <= j) g[i][j] = max(g[i][j], g[i + 1][j - toys[i].v * k] + toys[i].w * k); else break; } cin>> q; int x,y; while(q--){ cin>>x;cin>>y;x++; int ans = 0; for(int i=0;i<=y;i++){ ans = max(ans,f[x-1][i]+g[x+1][y-i]); } cout<<ans<<endl; } return 0; }```