题解 | #购物单#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int n = sc.nextInt();
        if (n <= 0 || money <= 0) {
            System.out.println(0);
            return;
        }
        Good[] goods = new Good[n + 1];
        // 找出最低价
        int minV = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt();// 表示物品价格
            int p = sc.nextInt();// 表示物品重要度
            int q = sc.nextInt();// 表示物品是否主件
            goods[i] = new Good(v, p, q);
            minV = Math.min(minV, v);
        }
        // 当钱不够买最便宜的物品时
        if (money < minV) {
            System.out.println(0);
            return;
        }
        for (int i = 1; i <= n; i++) {
            int q = goods[i].q;
            if (q > 0) {
                if (goods[q].a1 == 0) {
                    goods[q].setA1(i);
                } else {
                    goods[q].setA2(i);
                }
            }
        }

        int[][] dp = new int[n + 1][money + 1];
        for (int i = 1; i <= n; i++) {
            // 记录4种情况下的价值
            int v = 0, v1 = 0, v2 = 0, v3 = 0;
            // 记录4种情况下的满意度
            int tempdp = 0, tempdp1 = 0, tempdp2 = 0, tempdp3 = 0;

            // 当前商品价值
            v = goods[i].v;
            // 当前商品满意度
            tempdp = goods[i].p * v;

            int a1 = goods[i].a1;
            if (a1 != 0) {
                //主件加附件1后的价值
                v1 = goods[a1].v + v;
                //主件加附件1后的满意度
                tempdp1 = tempdp + goods[a1].v * goods[a1].p;
            }

            int a2 = goods[i].a2;
            if (a2 != 0) {
                //主件加附件2后的价值
                v2 = goods[a2].v + v;
                //主件加附件2后的满意度
                tempdp2 = tempdp + goods[a2].v * goods[a2].p;
            }

            if (a1 != 0 && a2 != 0) {
                //主件加附件1和附件2后的价值
                v3 = goods[a1].v + goods[a2].v + v;
                tempdp3 = tempdp + goods[a1].v * goods[a1].p + goods[a2].v * goods[a2].p;
            }

            // j表示价钱，从最低价开始遍历；因为物品价格是10的倍数，故j每次增长10，减少遍历次数
            for (int j = minV; j <= money; ) {
                if (goods[i].q > 0) {   //当物品i是附件时,相当于跳过
                    dp[i][j] = dp[i - 1][j];
                    j += 10;
                } else {
                    // 初始赋值为上一次的最大满意度
                    dp[i][j] = dp[i - 1][j];
                    // 当前的钱j比物品价值大时，统计最大满意度：上一个物品的满意度对比剩下的钱的满意度加当前物品满意度
                    if (j >= v && v != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v] + tempdp);
                    }
                    // 对比4种情况下得最大满意度
                    if (j >= v1 && v1 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + tempdp1);
                    }
                    if (j >= v2 && v2 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + tempdp2);
                    }
                    if (j >= v3 && v3 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + tempdp3);
                    }
                    j += 10;
                }
            }
        }
        System.out.println(dp[n][money]);


    }


    /**
     * 定义物品类
     */
    private static class Good {
        public int v;  //物品的价格
        public int p;  //物品的重要度
        public int q;  //物品的主附件ID

        public int a1 = 0;   //附件1ID
        public int a2 = 0;   //附件2ID

        public Good(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }

        public void setA1(int a1) {
            this.a1 = a1;
        }

        public void setA2(int a2) {
            this.a2 = a2;
        }
    }
}