题解 | #购物单#

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

#define MAX(a,b)    ((a>b)?(a):(b))
// int MAX(int a,int b) 
// {
//     return a>b?a:b;
// }

int main(void)
{
    int N,m; //预算 和 物品个数
    scanf("%d %d",&N,&m);
    N = N/10;
//穷举所有情况
    //四种情况
    //1. 主件
    //2. 主件+附件1
    //3. 主件+附件2
    //4. 主件+附件1+附件2
    int value[m][4];
    int price[m][4];
    memset(price,0,sizeof(price));
    memset(value,0,sizeof(value));
    int v, p, q;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&v,&p,&q);
        v = v/10;
        if(!q)  //主件
        {
            price[i][0]=v;
            value[i][0]=p * v;
        }else
        {
             if(price[q-1][1]==0)
             {
                price[q-1][1]=v;
                value[q-1][1]=p*v;
             }else
             {
                price[q-1][2]=v;
                value[q-1][2]=p*v;

                price[q-1][3]=price[q-1][1]+price[q-1][2];
                value[q-1][3]=value[q-1][1]+value[q-1][2];
             }
        }
    }

    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 1 ; j < 4 ; j++)
        {
            price[i][j] += price[i][0];
            value[i][j] += value[i][0];
        }
    }
    //得到每种物品的所有选择情况 price[m+1][4] 和对应价值 value[m+1][4]
    //其中附件的序号价格价值均为0 因为其不能单独购买

//动态规划数组
    int dp[m+1][N+1];  //前i件物品在N+10的预算下的最大价值
    memset(dp,0,sizeof(dp));
    int maxValue=0;
//至下而上穷举方案  并记录于数组中
    for(int i=1;i<m+1;i++)    //只有i件物品可供选 只有主件可以买
    {
        for(int j = 1;j<N+1;j++)    //只有j元预算的选择
        {
            maxValue = dp[i-1][j];  //假设最大价值为当前预算下前i件商品的最大价值
            for(int k=0;k<4;k++)    //主件需要考虑4种情况
            {
                if(k>0 && price[i-1][k]==price[i-1][0]) break; //没有附件
                if(j>=price[i-1][k]) //预算够了才能买
                {
                    maxValue = MAX(maxValue,dp[i-1][j-price[i-1][k]] + value[i-1][k]);
                }
            }
            dp[i][j]=maxValue;
        }
    }

    printf("%d",dp[m][N]*10);
    return 0;
}