题解 | 购物单

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

int main() {
    int m, n;
    while (cin >> m >> n) { // 注意 while 处理多个 case
        vector<vector<int>>price(n+1,vector<int>(3,0));
        vector<vector<int>>multiprice(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;
            multiprice[i][0]=a*b;}
            else {
            if(price[c][1]==0)
            {price[c][1]=a;
             multiprice[c][1]=a*b;}
             else {
             {price[c][2]=a;
             multiprice[c][2]=a*b;
             }
             }
            }
        }
        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];int b=multiprice[i][0];
                int c=price[i][1];int d=multiprice[i][1];
                int e=price[i][2];int f=multiprice[i][2];
                dp[i][j]=(j>=a)?max(dp[i-1][j-a]+b,dp[i-1][j]):dp[i-1][j];
                dp[i][j]=(j>=a+c)?max(dp[i-1][j-a-c]+b+d,dp[i][j]):dp[i][j];
                dp[i][j]=(j>=a+e)?max(dp[i-1][j-a-e]+b+f,dp[i][j]):dp[i][j];
                dp[i][j]=(j>=a+c+e)?max(dp[i-1][j-a-c-e]+b+d+f,dp[i][j]):dp[i][j];
            }
        }
        cout <<dp[n][m]<< endl;
    }
}
// 64 位输出请用 printf("%lld")