题解 | #购物单#

一开始把题目想复杂了，没看到最多只有两个附件，只有两个附件的话，购买一个主件最多有四种情况

/***HJ16购物单***/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    enum{price, importance, master, adj1, adj2}; //用枚举变量代表下表，省的后面需要看不同下表代表啥
    int N, m;
    scanf(" %d %d", &N, &m);
    N /= 10;
    int list[m+1][5]; //这里将数组从3个扩大至5个，后两个用于存储附件位置，方便后面扫描物品时进行计算
    memset(list, 0, sizeof(list));
    int i, j, k;
    //这里考虑主件可能会在附件之后输入，因此先读完数据之后再进行处理
    for(i = 1; i <= m; i++){
        scanf(" %d %d %d", &list[i][price], &list[i][importance], &list[i][master]);
        list[i][price] /= 10;
        list[i][importance] *= list[i][price];
        if(list[i][master]) list[list[i][master]][list[list[i][master]][adj1] ? adj2 : adj1] = i;
    }

    int dp[N+1], sum[4][2], count, child1, child2;
    memset(dp, 0, sizeof(dp));
    for(i = 1; i <= m; i++){
        memset(sum, 0, sizeof(sum));
        count = 0;
        if(list[i][master]) continue;
        sum[count][price] = list[i][price];
        sum[count][importance] = list[i][importance];
        count++;
        child1 = list[i][adj1];
        child2 = list[i][adj2];
        if(child1 && list[child1][price]+list[i][price] <= N){
            sum[count][price] = list[child1][price]+list[i][price];
            sum[count][importance] = list[child1][importance]+list[i][importance];
            count++;
        }
        if(child2 && list[child2][price]+list[i][price] <= N){
            sum[count][price] = list[child2][price]+list[i][price];
            sum[count][importance] = list[child2][importance]+list[i][importance];
            count++;
        }
        if(child1 && child2 && list[child1][price]+list[child2][price]+list[i][price] <= N){
            sum[count][price] = list[child1][price]+list[child2][price]+list[i][price];
            sum[count][importance] = list[child1][importance]+list[child2][importance]+list[i][importance];
            count++;
        }
        for(j = N; j > 0; j--){
            for(k = 0; k < count; k++){
                if(j >= sum[k][price]) dp[j] = dp[j] > dp[j-sum[k][price]]+sum[k][importance] ? dp[j] : dp[j-sum[k][price]]+sum[k][importance];
            }
        }
    }
    printf("%d", dp[N]*10);
    return 0;
}