题解 | #购物单#

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

int main() {
    int N, m;

    while (cin >> N >> m) { // 注意 while 处理多个 case

        vector<vector<int> > prices(m+1, vector<int>(3, 0));
        vector<vector<int> > pricesXimportance(m+1, vector<int>(3, 0));
        
        for(int i=1; i<=m; i++){
            int v, p, q;
            cin>>v>>p>>q;
            if (q==0){
                prices[i][0] = v;
                pricesXimportance[i][0]=p*v;
            }else{

                if(prices[q][1]==0){
                    prices[q][1] = v;
                    pricesXimportance[q][1] = p*v;
                }else{
                    prices[q][2]=v;
                    pricesXimportance[q][2]=p*v;
                }

            }
        }

        // for(int i=0; i<=m; i++){
        //     for(int j=0; j<3; j++){
        //         cout<<prices[i][j];
        //     }
        //     cout<<endl;
        // }


        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++){
                dp[i][j] = j>=prices[i][0]?max(dp[i-1][j-prices[i][0]]+pricesXimportance[i][0], dp[i-1][j]):dp[i-1][j];
                dp[i][j] = j>=(prices[i][0]+prices[i][1])?max(dp[i-1][j-prices[i][0]-prices[i][1]]+pricesXimportance[i][0]+pricesXimportance[i][1], dp[i][j]):dp[i][j];
                dp[i][j] = j>=(prices[i][0]+prices[i][2])?max(dp[i-1][j-prices[i][0]-prices[i][2]]+pricesXimportance[i][0]+pricesXimportance[i][2], dp[i][j]):dp[i][j];
                dp[i][j] = j>=(prices[i][0]+prices[i][1]+prices[i][2])?max(dp[i-1][j-prices[i][0]-prices[i][1]-prices[i][2]]+pricesXimportance[i][0]+pricesXimportance[i][1]+pricesXimportance[i][2], dp[i][j]):dp[i][j];
            }
        }


        cout<<dp[m][N]<<endl;


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