题解 | #购物单#

#include <stdio.h>
#include <string.h>
int max(int n,int m)
{
    if(n>m)
        return n;
    else
        return m;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int priece[61][4]={0},weight[61][4]={0},dp[56666]={0};
    for (int i = 0; i <m; i++) {
        int v,p,q;
        scanf("%d%d%d",&v,&p,&q);
        if(q==0)
        {
            priece[i][0]=v;
            weight[i][0]=v*p;
        }
        else
        {
            if(priece[q-1][1]==0)
            {
                priece[q-1][1]=v;
                weight[q-1][1]=v*p;
            }
            else
            {
                priece[q-1][2]=v;
                weight[q-1][2]=v*p;
                priece[q-1][3]=priece[q-1][1]+priece[q-1][2];
                weight[q-1][3]=weight[q-1][1]+weight[q-1][2];
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if(priece[i][0]!=0)
        {
            for (int j = 1; j < 4; j++)
            {
                priece[i][j]+=priece[i][0];
                weight[i][j]+=weight[i][0];
            }
        }
    }
    for (int l = 0; l < m; l++) {
        if(priece[l][0]!=0)
        {
            for (int i = n; i>=0; i-=10) {
                for (int j = 0; j < 4; j++) {
                    if(i>= priece[l][j])
                    {
                        dp[i]= max(dp[i],weight[l][j]+dp[i-priece[l][j]]);
                    }
                }
            }
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}