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

int max(int a, int b) { return a > b ? a : b; }

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // v[i][0]=价格, v[i][1]=重要度, v[i][2]=主件编号(0表示主件)
    int v[65][3] = {0};      // 原始输入
    int price[65] = {0};     // 价格
    int imp[65] = {0};       // 重要度
    int q[65] = {0};         // 主件编号
    
    // 存储每个主件的附件
    int attach[65][3];       // attach[i][0/1] 表示主件i的两个附件编号
    int att_cnt[65] = {0};   // 主件i的附件数量
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &price[i], &imp[i], &q[i]);
        if (q[i] != 0) {
            // 是附件，加入对应主件的附件列表
            int master = q[i];
            attach[master][att_cnt[master]++] = i;
        }
    }
    
    // dp[j] 表示预算为j时的最大满意度
    int dp[32000] = {0};
    
    // 遍历每个主件（分组）
    for (int i = 1; i <= m; i++) {
        if (q[i] != 0) continue;  // 跳过附件，只处理主件
        
        // 倒序遍历预算（0-1背包）
        for (int j = n; j >= 0; j--) {
            // 选择1：不选
            // 选择2：只选主件
            if (j >= price[i]) {
                dp[j] = max(dp[j], dp[j - price[i]] + price[i] * imp[i]);
            }
            
            // 选择3：主件 + 附件1
            if (att_cnt[i] >= 1 && j >= price[i] + price[attach[i][0]]) {
                dp[j] = max(dp[j], dp[j - price[i] - price[attach[i][0]]] 
                    + price[i] * imp[i] + price[attach[i][0]] * imp[attach[i][0]]);
            }
            
            // 选择4：主件 + 附件2
            if (att_cnt[i] >= 2 && j >= price[i] + price[attach[i][1]]) {
                dp[j] = max(dp[j], dp[j - price[i] - price[attach[i][1]]] 
                    + price[i] * imp[i] + price[attach[i][1]] * imp[attach[i][1]]);
            }
            
            // 选择5：主件 + 两个附件
            if (att_cnt[i] >= 2 && j >= price[i] + price[attach[i][0]] + price[attach[i][1]]) {
                dp[j] = max(dp[j], dp[j - price[i] - price[attach[i][0]] - price[attach[i][1]]] 
                    + price[i] * imp[i] 
                    + price[attach[i][0]] * imp[attach[i][0]]
                    + price[attach[i][1]] * imp[attach[i][1]]);
            }
        }
    }
    
    printf("%d\n", dp[n]);
    return 0;
}

DP 解法思路

定义状态

dp[j] = 预算为 j 元时，能获得的最大满意度

转移方程

对于每件物品，你有两个选择：

不买：dp[j] 不变

买：dp[j] = max(dp[j], dp[j-价格] + 满意度)

但本题有依赖关系（附件必须先买主件），所以把主件和它的附件当成一组：

每组有 5 种选择：

对每种选择，更新 dp 数组。

为什么倒序遍历预算？

防止重复选同一件物品。如果正序：

dp[10] 用了物品 A

更新 dp[20] 时，可能又用到 dp[10]，导致 A 被选了两次

倒序确保每件物品只选一次（0-1背包）。