题解 | #购物单#

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

int main() {
    int n,m;
    cin>>n>>m;
    
    n=n/10;
    vector<vector<int>> price(61,vector<int>(3,0));
    vector<vector<int>> value(61,vector<int>(3,0));
    for (int i = 1;i<=m;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        a /=10; b*=a;
        if(c==0){
            price[i][0] = a;
            value[i][0] = b;
        }else{
            if(price[c][1]==0){
                price[c][1] = a;
                value[c][1] = b;
            }else{
                price[c][2] = a;
                value[c][2] = b;
            }
        }
    }
    //记录好价格/价值数组
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<=n;j++){
            int d = price[i][0],x = value[i][0];
            int e = price[i][1],y = value[i][1];
            int f = price[i][2],z = value[i][2];
            dp[i][j] = j>=d?max(dp[i-1][j],dp[i-1][j-d]+x):dp[i-1][j];
            dp[i][j] = j>=(d+e)?max(dp[i][j],dp[i-1][j-d-e]+x+y):dp[i][j];
            dp[i][j] = j>=(d+f)?max(dp[i][j],dp[i-1][j-d-f]+x+z):dp[i][j];
            dp[i][j] = j>=(d+e+f)?max(dp[i][j],dp[i-1][j-d-e-f]+x+y+z):dp[i][j];
        }
    }
    cout<<dp[m][n]*10;

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

不是很熟悉，记录一下