题解 | #购物单#

#include<bits/stdc++.h>
#include <vector>
using namespace std;
int money,types,important;
int p[60];
int s[60];
int f[60];//f[i]==0代表是附属品
int main()
{
    while(cin>>money>>types)
    {
        for(int i=1;i<=types;i++)
        {
            cin>>p[i]>>important>>f[i];
            s[i]=p[i]*important;
        }
        vector<int> dp(money+1,0);
        for(int i=1;i<=types;i++)
        {
            for(int j=money;j>=0;j-=10)
            {
                if(f[i]==0)//如果是主件
                {
                    if(j-p[i]>=0)//如果能放下主件
                    dp[j]=max(dp[j],dp[j-p[i]]+s[i]);
                    int f1=0,f2=0;//假装有两个附属品
                    for(int k=1;k<=types;k++)
                    {
                        if(f[k]==i&&f1==0){ ;f1=k;};//找到第一个附属品
                        if(f[k]==i&&f1!=k) f2=k;//找到第二个附属品
                        if(f1&&f2) break;  //找到两个，就不用继续了
                    }
                    if(j-p[i]-p[f1]>=0) //放得下第一个附件
                    dp[j]=max(dp[j],dp[j-p[i]-p[f1]]+s[i]+s[f1]);
                    if(j-p[i]-p[f2]>=0)//放得下第二个附近
                    dp[j]=max(dp[j],dp[j-p[i]-p[f2]]+s[i]+s[f2]);
                    if(j-p[i]-p[f1]-p[f2]>=0)//放得下两个附件
                    dp[j]=max(dp[j],dp[j-p[i]-p[f1]-p[f2]]+s[i]+s[f1]+s[f2]);
                }
            }
        }
        cout<<dp[money]<<endl;
    }
}