题解 | #购物单#

//主要思想是动态规划 01背包的变种，在当拥有附件时主件放入背包将分情况讨论
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N,m;
    cin>>N>>m;
    int pi[61][4]={0},we[61][4]={0},ac[61]={0},n0=0;//pi（i，j）表示第件主商品 第j种情况，j=0,1,2,3分别表示无附件，附件1,2,1+2；
                                            //ac【x】 表示x号商品附件数，默认为0
    int dp[61][32000]={0};
    for(int i=1;i<=m;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        if(q==0) //主件
        {
            pi[i][0]=v;
            we[i][0]=p*v;
        }
        else //附件
        {
            ac[q]+=1;
            if(ac[q]==1)
            {
                pi[q][1]=v;//记录附件价格
                we[q][1]=p*v;
            }
            else {
                pi[q][2]=v;
                we[q][2]=p*v;
                pi[q][3]=v+pi[q][1];
                we[q][3]=p*v+we[q][1];
            }

        }
    }
    for(int x=1;x<=m;x++)
    {
        for(int y=0;y<=N;y++)
        {
            if(pi[x][0]!=0 && pi[x][0]<=y)
            {
                switch (ac[x]) {
                    case 0:
                    dp[x][y]=max(dp[x-1][y],we[x][0]+dp[x-1][y-pi[x][0]]);
                    break;
                    case 1:
                    if((pi[x][1]+pi[x][0])<=y)
                    {
                        dp[x][y]=max(dp[x-1][y],  max(we[x][0]+dp[x-1][y-pi[x][0]],we[x][1]+we[x][0]+dp[x-1][y-pi[x][1]-pi[x][0]]));
                    }else
                    dp[x][y]=max(dp[x-1][y],we[x][0]+dp[x-1][y-pi[x][0]]);
                    break;
                    case 2:
                    dp[x][y]=max(dp[x-1][y],we[x][0]+dp[x-1][y-pi[x][0]]);
                    if(pi[x][1]+pi[x][0]<=y)
                    dp[x][y]=max(dp[x][y],we[x][1]+we[x][0]+dp[x-1][y-pi[x][1]-pi[x][0]]);
                    if(pi[x][2]+pi[x][0]<=y)
                    dp[x][y]=max(dp[x][y],we[x][2]+we[x][0]+dp[x-1][y-pi[x][2]-pi[x][0]]);
                    if(pi[x][3]+pi[x][0]<=y)
                    dp[x][y]=max(dp[x][y],we[x][3]+we[x][0]+dp[x-1][y-pi[x][3]-pi[x][0]]);
                    break;
                }
            }
            else 
            {
                dp[x][y]=dp[x-1][y];
            }
        }
        
    }
    //int x=1,y=300;
    //cout<<max(dp[x-1][y],we[x][0]+dp[x-1][y-pi[x][0]])<<endl;
    cout<<dp[m][N]<<endl;
    /* for(int i=1;i<=m;i++)//测试用
    {
        if(ac[i]==0&&pi[i][0]!=0)
        {
            cout<<i<<' '<<"单主 "<<pi[i][0]<<" "<<we[i][0]<<endl;
        }
        else if(ac[i]==1)
        {
            cout<<i<<' '<<"单主 "<<pi[i][0]<<" "<<we[i][0]<<endl;
            cout<<i<<' '<<"+1 "<<pi[i][1]<<" "<<we[i][1]<<endl;
        }
        else if(ac[i]==2)
        {
            cout<<i<<' '<<"单主 "<<pi[i][0]<<" "<<we[i][0]<<endl;
            cout<<i<<' '<<"+1 "<<pi[i][1]<<" "<<we[i][1]<<endl;
            cout<<i<<' '<<"+2 "<<pi[i][2]<<" "<<we[i][2]<<endl;
            cout<<i<<' '<<"+1+2 "<<pi[i][3]<<" "<<we[i][3]<<endl;
        }

    }*/

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