相信大家都能看出这是多重背包

但问题是怎么去掉某个玩偶

去掉玩偶就可以单独求前面的和后面的，只需要一正一反两个背包就好了，剩下就是正常的多重背包。

AC代码

#include <bits/stdc++.h>
using namespace std;

int fl[100010][1010],fr[100010][1010]；//正反背包
int v[100010],w[100010],cnt,l[1010],r[1010];

int main(){
    int n,a,b,c,q,d,e,maxx;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a >> b >> c;
        l[i] = cnt;
        //按1 2 4 8...拆成01背包
        int sum = 1;
        while(c>sum){
            cnt++;
            w[cnt] = a*sum,v[cnt] = b*sum;
            c-=sum;
            sum<<=1;
        }
        cnt++;
        w[cnt] = a*c,v[cnt] = b*c;
        r[i] = cnt+1;
    }
  //正一遍
    for(int i = 1;i <= cnt;i++){
        for(int j = 1;j <= 1000;j++){
            if(j<w[i]) fl[i][j] = fl[i-1][j];
            else fl[i][j] = max(fl[i-1][j],fl[i-1][j-w[i]]+v[i]);
        }
    }
  //反一遍
    for(int i = cnt;i >= 1;i--){
        for(int j = 1;j <= 1000;j++){
            if(j<w[i]) fr[i][j] = fr[i+1][j];
            else fr[i][j] = max(fr[i+1][j],fr[i+1][j-w[i]]+v[i]);
        }
    }
    cin >> q;
    while(q--){
        cin >> d >> e;
        d++;
        maxx = 0;
        for(int i = 0;i <= e;i++){//分配前后容量
            maxx = max(maxx,fl[l[d]][i]+fr[r[d]][e-i]);
        }
        cout << maxx << endl;
    }
    return 0;
}