题解 | 购物单

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
const int N=65;
int n,m;
int v[N],w[N],q[N];
vector<int> extra[N];
vector<int> main_id;
int dp[3005];
int main() {
    scanf("%d%d",&m,&n);//预算，个数
    m/=10;
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&v[i],&w[i],&q[i]);
        v[i]/=10;
        if(q[i]!=0){
            extra[q[i]].push_back(i);
        }
        else{
            main_id.push_back(i);
        }
    }
    for(int i:main_id){
        vector<pair<int,int>> vw;
        vw.emplace_back(v[i],v[i]*w[i]);
        for(int j:extra[i]){
            for(int k=0,t=vw.size();k<t;++k){
                vw.emplace_back(vw[k].first+v[j],vw[k].second+v[j]*w[j]);
            }
        }
        for(int j=m;j>=v[i];--j){
            for(auto [price,weight]:vw){
                if(j-price>=0){
                    dp[j]=max(dp[j],dp[j-price]+weight);
                }
            }
        } 
    }
    int res=0;
    for(int i=1;i<=m;++i){
        res=max(res,dp[i]);
    }
    cout<<res*10<<endl;
}