题解 | #购物单#

import java.util.Scanner;
// refer blog,  https://blog.nowcoder.net/n/e82df6de55184248a2964a260b5c08ee?f=comment
class Goods {
    boolean main = false;
    int v;//价格
    int p;//重要程度
    //两个附件
    int a1 = -1;
    int a2 = -1;


}

public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int m = scanner.nextInt();
        Goods[] goods = new Goods[m];
        for (int i = 0; i < m; i++) {
            goods[i] = new Goods();
        }
        for (int i = 0; i < m; i++) {
            int v = scanner.nextInt();
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            goods[i].v = v;//价格
            goods[i].p = p * v;//满意度
            if (q == 0) {
                goods[i].main = true;
            } else if (goods[q - 1].a1 == -1) {
//                goods[i].a1=q-1;
                goods[q - 1].a1 = i;
            } else
//                goods[i].a2=q-1;
                goods[q - 1].a2 = i;
        }
        int dp[][] = new int[m + 1][N + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= N; j++) {
                //不选该商品
                dp[i][j] = dp[i - 1][j];
                //是附件,选到主件的时候 会被讨论到
                if (!goods[i - 1].main) {
                    continue;
                }

                //选择主件
                if (j >= goods[i - 1].v) {

                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i - 1].v] + goods[i - 1].p);

                }

                //选择主件和附件1
                if (goods[i - 1].a1 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a1].v) {
                    dp[i][j] = Math.max(dp[i][j],
                                        dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v] + goods[i - 1].p +
                                        goods[goods[i - 1].a1].p);
                }
                //选择主件和附件2
                if (goods[i - 1].a2 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a2].v) {
                    dp[i][j] = Math.max(dp[i][j],
                                        dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a2].v] + goods[i - 1].p +
                                        goods[goods[i - 1].a2].p);
                }
                //选择主件和附件1和附件2
                if (goods[i - 1].a1 != -1 && goods[i - 1].a2 != -1 &&
                        j >= goods[i - 1].v + goods[goods[i - 1].a1].v + goods[goods[i - 1].a2].v) {
                    dp[i][j] = Math.max(dp[i][j],
                                        dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v - goods[goods[i -
                                                  1].a2].v] + goods[i - 1].p + goods[goods[i - 1].a1].p + goods[goods[i -
                                                          1].a2].p);
                }


            }


        }
        System.out.println(dp[m][N]);


//        for (int i = 0; i < goods.length; i++) {
//            System.out.print(goods[i].v+" ");
//            System.out.print(goods[i].p+" ");
//            System.out.print(goods[i].a1+" ");
//            System.out.print(goods[i].a2+" ");
//            System.out.println();
//        }


    }


}