题解 | #购物单#

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

int main() {
    int v, n;
    cin>>v>>n;
    v/=10;
    int weight[n][3];
    int value[n][3];
    for(int i=0;i<n;i++)
    {
        weight[i][2]=0;
        value[i][2]=0;
        weight[i][1]=0;
        value[i][1]=0;
    }
    int q[n];
    for(int i=0;i<n;i++)
    {
        cin>>weight[i][0];
        weight[i][0]/=10;
        cin>>value[i][0];
        value[i][0]*=weight[i][0]*10;
        cin>>q[i];
        if(q[i]>0&&weight[q[i]-1][1]!=0)
        {
            weight[q[i]-1][2]=weight[i][0];
            value[q[i]-1][2]=value[i][0];
        }
        if(q[i]>0&&weight[q[i]-1][1]==0)
        {
            weight[q[i]-1][1]=weight[i][0];
            value[q[i]-1][1]=value[i][0];
        }
        
    }
    vector<int> dp(v+1,0);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        if(q[i]>0) continue;
        for(int j=v;j>=1;j--)
        {
            if(j>=weight[i][0])
            {
                dp[j]=max(dp[j],dp[j-weight[i][0]]+value[i][0]);
            }
            if(j>=weight[i][1]+weight[i][0])
            {
                dp[j]=max(dp[j],dp[j-weight[i][1]-weight[i][0]]+value[i][1]+value[i][0]);
            }
            if(j>=weight[i][2]+weight[i][0])
            {
                dp[j]=max(dp[j],dp[j-weight[i][2]-weight[i][0]]+value[i][2]+value[i][0]);
            }
            if(j>=weight[i][1]+weight[i][2]+weight[i][0])
            {
                dp[j]=max(dp[j],dp[j-weight[i][1]-weight[i][2]-weight[i][0]]+value[i][1]+value[i][2]+value[i][0]);
            }
        }
    }
    cout<<dp[v];
}
// 64 位输出请用 printf("%lld")