luogu p4095

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;
}```