题解 | #购物单#

#include <iostream>
#include<vector>

using namespace std;

int main() {
    int N,m;//金额，物品数量
    cin>>N>>m;
    N/=10;
    vector<vector<int>> prices(m+1,vector<int>(3,0));//00主件，01附件1，02附件2
    vector<vector<int>> weight(m+1,vector<int>(3,0));
    //初始化主件和附件关系
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c==0)//是主见
        {
            prices[i][0]=a/10;
            weight[i][0]=b;
        }
        else{//遇到了附件
            if(prices[c][1]!=0){//如果附件1已经遇到
                 prices[c][2]=a/10;
                 weight[c][2]=b;
            }
            else{
                prices[c][1]=a/10;
                weight[c][1]=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=prices[i][0],b=prices[i][1],c=prices[i][2];
            int d=weight[i][0],e=weight[i][1],f=weight[i][2];
            dp[i][j]=j>=a? std::max(dp[i-1][j-a]+a*d,dp[i-1][j]):dp[i-1][j];//仅主件
            dp[i][j]=j>=a+b? std::max(dp[i-1][j-a-b]+a*d+b*e,dp[i][j]):dp[i][j];//加上附件1
            dp[i][j]=j>=a+c? std::max(dp[i-1][j-a-c]+a*d+c*f,dp[i][j]):dp[i][j];//加上附件2
            dp[i][j]=j>=a+b+c? std::max(dp[i-1][j-a-b-c]+a*d+b*e+c*f,dp[i][j]):dp[i][j];//都加上
        }
    }
    cout<<dp[m][N]*10<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")