题解 | #购物单#

#include<iostream>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
int dp[62][32010];
struct good
{
    int v,w;
};
int main()
{
    int N,m;
    cin>>N>>m;
    
    unordered_map<int,vector<good>> tmp,goods;
    
    for(int i=1;i<=m;i++)
    {
        int v,q,p;
        cin>>v>>p>>q;
        if(q==0) goods[i].push_back({v,v*p});
        else tmp[q].push_back({v,v*p});
    }
    for(auto x:tmp)
    {
        int index=x.first;
        vector<good> vc=x.second;
        if(vc.size()==1)
        {
            goods[index].push_back({vc[0].v+goods[index][0].v,vc[0].w+goods[index][0].w});
        }
        else if(vc.size()==2)
        {
            goods[index].push_back({vc[0].v+goods[index][0].v,vc[0].w+goods[index][0].w});
            goods[index].push_back({vc[1].v+goods[index][0].v,vc[1].w+goods[index][0].w});
            goods[index].push_back({vc[0].v+vc[1].v+goods[index][0].v,vc[0].w+vc[1].w+goods[index][0].w});
        }
    }
    //这样一来，所有物品就都放好了。
    int idx=1;
    for(auto x:goods)
    {
        auto vc=x.second;
        int len=vc.size();
        for(int j=0;j<=N;j++)
        {
            dp[idx][j]=dp[idx-1][j];//不选
            for(int k=0;k<len;k++)
            {
                if(j>=vc[k].v) dp[idx][j]=max(dp[idx][j],dp[idx-1][j-vc[k].v]+vc[k].w);
            }
        }
        idx++;
    }
    cout<<dp[idx-1][N];
}