题解 | #购物单#

#include<iostream>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main(){
    int N,m;
    cin >> N >> m;
    N/=10;
    vector<int> V,P,Q;
    map<int,vector<int>> dict;
    int v,p,q;
    for(int i=0;i<m;i++){
        cin >> v >> p >> q;
        v/=10;
        V.push_back(v);
        P.push_back(p);
        Q.push_back(q);
        dict[q].push_back(i);
     }
    int id_1,id_2;
    int len=dict[0].size();
    vector<vector<pair<int,int>>>rec(len);
    for(int i=0;i<len;i++){
        int x=dict[0][i];
        rec[i].push_back(make_pair(V[x],V[x]*P[x]));
        if(dict[x+1].size()==2){
            id_1=dict[x+1][0];
            id_2=dict[x+1][1];
            rec[i].push_back(make_pair(V[id_1]+V[x],P[id_1]*V[id_1]+P[x]*V[x]));
            rec[i].push_back(make_pair(V[id_2]+V[x],P[id_2]*V[id_2]+P[x]*V[x]));
            rec[i].push_back(make_pair(V[id_1]+V[id_2]+V[x],P[id_1]*V[id_1]+P[id_2]*V[id_2]+P[x]*V[x]));   
        }
        else if(dict[x+1].size()==1) {
            id_1=dict[x+1][0];
            rec[i].push_back(make_pair(V[id_1]+V[x],P[id_1]*V[id_1]+P[x]*V[x]));
        }
    }
    
    vector<vector<int>> dp(len+1,vector<int>(N+1,0));
    for(int i=1;i<=len;i++){
        for(int j=1;j<=N;j++){
            int cur=0;
            for(int k=0;k<rec[i-1].size();k++){
                int price=rec[i-1][k].first;
                int good=rec[i-1][k].second;
                if(j-price>=0){
                    cur=max(cur,dp[i-1][j-price]+good);
                }
            }    
            dp[i][j]=max(dp[i-1][j],cur);   
        }
    }
    cout<<dp[len][N]*10;
    
}