题解 | #购物单#

/*
    第一次尝试，想错了、

#include <iostream>
#include <queue>
using namespace std;


int dp[65];
int v[65],w[65],value[65],q[65];
int vis[65];

class goods{
    public:
    int value,q;
    bool vis;
    int num;
    goods(int v,int q,bool vis,int num):value(v),q(q),vis(vis),num(num){};

    friend bool operator<(goods a,goods b){
        return a.value < b.value;
    }
};


priority_queue<goods> res;

void init(){

        fill(v,v+65,0);
        fill(w,w+65,0);
        fill(value,value+65,0);
        fill(q,q+65,0);
        fill(vis,vis+65,0);
        while(!res.empty()){
            res.pop();
        }
}

int main() {
    int n,m;
    while (cin >> n >> m) { // 注意 while 处理多个 case

        init();
        for(int i=0;i<m;i++){
            cin>>v[i]>>w[i]>>q[i];
            value[i] = v[i] * w[i];
            int num = q[i] == 0?i+1:0;
            goods tmp(value[i],q[i],vis[i],num);
            res.push(tmp);
        }
        while(!res.empty()){
            goods tmp = res.top();
            res.pop();
            cout<<tmp.num<< ' '<<tmp.value<<' '<<tmp.q<<' '<<tmp.vis<<endl;
        }

        while(n>=0 || !res.empty()){
             
        }


    }
    return 0;
}
// 64 位输出请用 printf("%lld")

*/






#include<iostream>
#include <vector>
using namespace std;

int main(){
    int N,M;
    cin>>M>>N;
    M/=10;
    vector<vector<int>> price(N+1,vector<int>(3,0));
    vector<vector<int>> value(N+1,vector<int>(3,0));
    for(int i=1;i<=N;i++){
        int v,p,q;
        cin>>v>>p>>q;
        if(q == 0){
            price[i][0] = v/10;
            value[i][0] = p; 
        }
        else {
            if(price[q][1] !=0){
                price[q][2] = v/10;
                value[q][2] = p;
            }
            else {
                price[q][1] = v/10;
                value[q][1] = p;
            }
        }    
    }
    vector<vector<int>> dp(N+1,vector<int>(M+1,0));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){


            int a = price[i][0],b=value[i][0];
            int c = price[i][1],d=value[i][1];
            int e = price[i][2],f=value[i][2];
            
            dp[i][j] = j>=a?max(dp[i-1][j-a] + a*b ,dp[i-1][j]):dp[i-1][j];
            dp[i][j] = j>=(a+c)?max(dp[i-1][j-a-c] + a*b + c*d,dp[i][j]):dp[i][j];
            dp[i][j] = j>=(a+e)?max(dp[i-1][j-a-e] + a*b + e*f,dp[i][j]):dp[i][j];
            dp[i][j] = j>=(a+c+e)?max(dp[i-1][j-a-c-e] + a*b + c*d + e*f,dp[i][j]):dp[i][j];
        }
    }
    
    cout<<dp[N][M]*10<<endl;

    return 0;
}