题解 | #购物单#

#include<stdio.h>
#include<string.h>
#define max(i,j) ((i>j) ? (i):(j))
int main(){
    int N=0,m=0;
    scanf("%d %d",&N, &m);
    N /= 10;
    int price[m+1][4];  //价格 主件 主件+附件1 主件+附件2 主件+附件1+附件2
    int pman[m+1][4];   // 满意度 主件  主件+附件1  主件+附件2  主件+附件1+附件2
    // 看了一下测试集，主件不一定在附件前，服了
    memset(price, 0, sizeof(price));
    memset(pman, 0, sizeof(pman));
    for(int i = 1; i<= m; i++){
        int a=0, b=0, c = 0;
        scanf("%d %d %d",&a,&b,&c);
        a /= 10;
        if(c==0){ //主件
            price[i][0] = a;
            pman[i][0] = a*b;
        }else if(price[c][1] == 0){ //附件1
            price[c][1] = a;
            pman[c][1] = a*b;
        }else{  //附件2 附件1+附件2
            price[c][2] = a;
            pman[c][2] = a*b;
            price[c][3] = price[c][1] + a;
            pman[c][3] = pman[c][1] + a*b;
        }
    }
    for(int i = 1; i<= m; i++){
        for(int k = 1; k <=3;k++){
            price[i][k] += price[i][0];
            pman[i][k] += pman[i][0];
        }
    }
    int dp[m+1][N+1];  //用N(j)奖金购买前m(i)个物品的总价值
    memset(dp, 0, sizeof(dp));  
    for(int i = 1; i< m+1;i++){
        for (int j = 1; j< N+1; j++){
            int max_val = dp[i-1][j];
            for(int k = 0; k < 4; k++){
                if(price[i][k] == 0){
                    break;
                }
                if(j >= price[i][k])
                    max_val = max(max_val, dp[i-1][j - price[i][k]] + pman[i][k]);
            }
            dp[i][j] = max_val;
            // printf("%d ,", dp[i][j]);
        }
        // printf("\n");
    }
    printf("%d",dp[m][N] * 10);
}

把附件和主件看成一体的，对于每个主件，只有四种选择

主件 主件+附件1 主件+附件2 主件+附件1+附件2

然后使用dp迭代使用j元选择前i件 商品的最大满意度dp(i,j)