题解 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        String line = in.nextLine();
        String[] strs = line.split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        int max = 0;
        Good[] goods = new Good[m + 1];
        // 初始化goods
        for (int i = 1; i <= m; i++) {
            String str = in.nextLine();
            String[] itemStr = str.split(" ");
            Good good = new Good();
            int v = good.v = Integer.parseInt(itemStr[0]);
            int p = good.p = Integer.parseInt(itemStr[1]);
            int q = good.q = Integer.parseInt(itemStr[2]);
            goods[i] = good;

        }
        for (int i = 1; i <= m; i++) {
            Good good = goods[i];
            int q = good.q;
            if ( q== 0) {
                good.main = true;
            } else if (goods[q].a1 == -1) {
                goods[q].a1 = i;
            } else {
                goods[q].a2 = i;
            }
        }
        int[][] dp = new int[m + 1][n / 10 + 1];
        for (int i = 1; i <= m; i++) {
            int v = goods[i].v;
            int p = goods[i].p;
            int q = goods[i].q;
            boolean main = goods[i].main;
            int a1 = goods[i].a1;
            int a2 = goods[i].a2;

            int v1 = 0, v2 = 0, v3 = 0, vp = 0, vp1 = 0, vp2 = 0, vp3 = 0;
            vp = v * p;

            if (a1 != -1) {
                v1 = v + goods[a1].v;
                vp1 = v * p + goods[a1].v * goods[a1].p;
            }

            if (a2 != -1) {
                v2 = v + goods[a2].v;
                vp2 = v * p + goods[a2].v * goods[a2].p;
            }

            if (a1 != -1 && a2 != -1) {
                v3 = v + goods[a1].v + goods[a2].v;
                vp3 = v * p + goods[a1].v * goods[a1].p + goods[a2].v * goods[a2].p;
            }


            for (int j = 1; j <= n / 10; j++) {
                dp[i][j] = dp[i - 1][j];
                if (!main) {
                    continue;
                }
                if (v != 0 && v <= j * 10) {
                    dp[i][j] = Math.max(dp[i][j], vp + dp[i - 1][j - v / 10]);
                }
                if (v1 != 0 && v1 <= j * 10) {
                    dp[i][j] = Math.max(dp[i][j], vp1 + dp[i - 1][j - v1 / 10]);
                }
                if (v2 != 0 && v2 <= j * 10) {
                    dp[i][j] = Math.max(dp[i][j], vp2 + dp[i - 1][j - v2 / 10]);
                }
                if (v3 != 0 && v3 <= j * 10) {
                    dp[i][j] = Math.max(dp[i][j], vp3 + dp[i - 1][j - v3 / 10]);
                }
            }
        }
        System.out.print(dp[m][n / 10]);
    }

}


class Good {
    protected int v;
    protected int p;
    protected int q;
    protected boolean main = false;
    protected int a1 = -1;
    protected int a2 = -1;




}