题解 | 购物单

#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 a,b,c;
        cin >> a >> b >> c;
        if(c == 0)
        {
            price[i][0] =a/10;
            value[i][0] =b;
        }
        else{
            if(price[c][1] == 0)
            {
                price[c][1] =a/10;
                value[c][1] =b;            
            }
            else{
                price[c][2] =a/10;
                value[c][2] =b;
            }
        }
    }
    
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++)
    {
        int a=price[i][0], b=value[i][0];
        if (a == 0) 
        {   
            // 跳过纯附件
            for(int j=0;j<=m;j++)
            {
                dp[i][j] = dp[i-1][j];
            }
            continue;
        }
        int c=price[i][1], d=value[i][1];
        int e=price[i][2], f=value[i][2];
    
        for(int j=0;j<=m;j++)
        {                
            int best = dp[i-1][j];
            if(j>=a) best = max(best, dp[i-1][j-a] + a*b);
            if(c!=0 && j>=a+c) best = max(best, dp[i-1][j-a-c] + a*b + c*d);
            if(e!=0 && j>=a+e) best = max(best, dp[i-1][j-a-e] + a*b + e*f);
            if(c!=0 && e!=0 && j>=a+c+e) best = max(best, dp[i-1][j-a-c-e] + a*b + c*d + e*f);
            dp[i][j] = best;
        }
    }

    cout<<dp[n][m]*10;

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