题解 | #购物单#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int money = in.nextInt();
        int n = in.nextInt();
        // 下标从1开始方便计算
        Good[] goods = new Good[n + 1];
        int i = 0;
        while (++i <= n) {
            goods[i] = new Good();
        }
        for (i = 1; i <= n; i++) {
            goods[i].cost = in.nextInt();
            goods[i].importance = in.nextInt();
            int q = in.nextInt();
            goods[i].main = q == 0;
            // 如果是附件 找到它的主件 设置该主件的附件ID
            if (!goods[i].main) {
                if (goods[q].a1 == 0) {
                    goods[q].a1 = i;
                } else {
                    goods[q].a2 = i;
                }
            }
        }
        int[][] dp = new int[n + 1][money + 1];
        for (i = 1; i <= n; i++) {
            int cost0, cost1 = 0, cost2 = 0, cost3 = 0;
            int dp0, dp1 = 0, dp2 = 0, dp3 = 0;
            // 只有主件
            cost0 = goods[i].cost;
            dp0 = cost0 * goods[i].importance;

            // 主件 + 一个附件1
            if (goods[i].a1 != 0) {
                cost1 = cost0 + goods[goods[i].a1].cost;
                dp1 = dp0 + goods[goods[i].a1].cost * goods[goods[i].a1].importance;
            }

            // 主件 + 一个附件2
            if (goods[i].a2 != 0) {
                cost2 = cost0 + goods[goods[i].a2].cost;
                dp2 = dp0 + goods[goods[i].a2].cost * goods[goods[i].a2].importance;
            }

            // 主件 + 两个附件
            if (goods[i].a1 != 0 && goods[i].a2 != 0) {
                cost3 = cost1 + cost2 - cost0;
                dp3 = dp1 + dp2 - dp0;
            }

            // 根据题意可得步长为10
            for (int j = 10; j <= money; j += 10) {
                // 附件直接跳过
                if (!goods[i].main) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= cost0 && cost0 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost0] + dp0);
                    }
                    if (j >= cost1 && cost1 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost1] + dp1);
                    }
                    if (j >= cost2 && cost2 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost2] + dp2);
                    }
                    if (j >= cost3 && cost3 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost3] + dp3);
                    }
                }
            }
        }
        System.out.println(dp[n][money]);
    }

    static class Good {
        // 花费、重要性、附件1、附件2
        int cost, importance, a1, a2;
        // 是否为主件
        boolean main;
    }
}