题解 | #购物单#

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N,m;
    cin>>N>>m;
    vector<vector<int>> price(m+1,vector<int>(3,0));
    vector<vector<int>> value(m+1,vector<int>(3,0));
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        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 a=price[i][0],b=value[i][0];
            int c=price[i][1],d=value[i][1];
            int e=price[i][2],f=value[i][2];
            dp[i][j]=j>=a?max(dp[i-1][j-a]+a*b,dp[i-1][j]):dp[i-1][j];
            dp[i][j]=j>=a+c?max(dp[i-1][j-a-c]+a*b+c*d,dp[i][j]):dp[i][j];
            dp[i][j]=j>=a+e?max(dp[i-1][j-a-e]+a*b+e*f,dp[i][j]):dp[i][j];
            dp[i][j]=j>=a+c+e?max(dp[i-1][j-a-e-c]+a*b+c*d+e*f,dp[i][j]):dp[i][j];
        }
    }
    cout<<dp[m][N]<<endl;
    return 0;
}