题解 | #购物单#

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

int N,m;

void max_satis(){
    int v,p,MS;
    vector<vector<int>> v_vet(m,vector<int> (1,0));
    vector<vector<int>> vp_vet(m,vector<int> (1,0));

    for(int i = 0; i < m; i++){
        cin >> v >> p >> MS;
        if(MS == 0){
            v_vet[i][0] = v;
            vp_vet[i][0] = v * p;
        }
        else{
            v_vet[MS-1].push_back(v);
            vp_vet[MS-1].push_back(v*p);
        }
    }

    vector<vector<int>> dp(m, vector<int>(N+1, 0));

    //初始化
    for(int j = v_vet[0][0]; j <= N; j++){
        if(j >= v_vet[0][0]+v_vet[0][1]+v_vet[0][2]) dp[0][j] = vp_vet[0][0]+vp_vet[0][1]+vp_vet[0][2];
        else if(j >= max(v_vet[0][0]+v_vet[0][1],v_vet[0][0]+v_vet[0][2]))    dp[0][j] = max(vp_vet[0][0]+vp_vet[0][1],vp_vet[0][0]+vp_vet[0][2]);
        else if(j >= min(v_vet[0][0]+v_vet[0][1],v_vet[0][0]+v_vet[0][2]))  dp[0][j] = (min(v_vet[0][0]+v_vet[0][1],v_vet[0][0]+v_vet[0][2]) == v_vet[0][0]+v_vet[0][1])?vp_vet[0][0]+vp_vet[0][1]:vp_vet[0][0]+vp_vet[0][2];
        else dp[0][j] = vp_vet[0][0];
    }

    for(int i = 1; i < m; i++){
        for(int j = 1; j < N+1; j++){
            //主
            if(v_vet[i][0] > j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j],dp[i-1][j-v_vet[i][0]]+vp_vet[i][0]);
            //主+附1
            if(v_vet[i][0] + v_vet[i][1] > j) dp[i][j] = dp[i][j];
            else dp[i][j] = max(dp[i][j],dp[i-1][j-v_vet[i][0]-v_vet[i][1]]+vp_vet[i][0]+vp_vet[i][1]);
            //主+附2
            if(v_vet[i][0] + v_vet[i][2] > j) dp[i][j] = dp[i][j];
            else dp[i][j] = max(dp[i][j],dp[i-1][j-v_vet[i][0]-v_vet[i][2]]+vp_vet[i][0]+vp_vet[i][2]);
            //主++附1+附2
            if(v_vet[i][0] + v_vet[i][1] + v_vet[i][2] > j) dp[i][j] = dp[i][j];
            else dp[i][j] = max(dp[i][j],dp[i-1][j-v_vet[i][0]-v_vet[i][1]-v_vet[i][2]]+vp_vet[i][0]+vp_vet[i][1]+vp_vet[i][2]);
        }
        
    }
    cout << dp[m-1][N] << endl;
}


int main() {
    cin >> N >> m;
    max_satis();
}
// 64 位输出请用 printf("%lld")