题解 | #购物单#

#include <math.h>
#include <stdio.h>
#include <string.h>

int main() {
    int money = 0,num = 0;
    int v,p,q;
    scanf("%d %d",&money,&num);

    int weight[num][4];
    int cost[num][4];

    memset(weight, 0, sizeof(weight));
    memset(cost,0,sizeof(cost));

    for(int i=0;i<num;i++)
    {
        scanf("%d %d %d",&v,&p,&q);
        if(q==0)
        {
            weight[i][0] = p*v;
            cost[i][0] = v;
        }else if(cost[q-1][1] == 0)
        {
            weight[q-1][1] = p*v;
            cost[q-1][1] = v;
        }else{
            weight[q-1][2] = p*v;
            cost[q-1][2] = v;

            weight[q-1][3] = weight[q-1][1]+v*p;
            cost[q-1][3] = cost[q-1][1]+v;
        }
    }

    for(int i = 0;i<num;i++)
    {
        if(cost[i][0]!=0)
        {
            for(int k=1;k<4;k++)
            {
                weight[i][k]+=weight[i][0];
                cost[i][k]+=cost[i][0];
            }
        }
    }

    /*for(int i=0;i<num;i++)
    {
        for(int j=0;j<4;j++)
        {
            printf("%d ",cost[i][j]);
        }
        printf("\n");
    }*/


    int dp[num+1][money+1];
    memset(dp,0,sizeof(dp));
    int max_val;

    for(int i =1;i<=num;i++)
    {
        
        for(int j =10;j<=money;j+=10)
        {
            max_val = dp[i-1][j];
            for(int k =0;k<4;k++)
            {
                if(j>=cost[i-1][k])
                max_val = fmax(max_val,dp[i-1][j-cost[i-1][k]]+weight[i-1][k]);          
            }
            dp[i][j] = max_val; 
        }
    }

    printf("%d",dp[num][money]);
}