题解 | #购物单#

import java.util.*;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int money = sc.nextInt();
            int goodCount = sc.nextInt();
            Good[] goods = new Good[goodCount + 1];
            for (int i = 1; i <= goodCount; i++) {
                goods[i] = new Good(sc.nextInt(), sc.nextInt(), sc.nextInt());
            }
            for (int i = 1; i <= goodCount; i++) {
                Good good = goods[i];
                if (good.q != 0) {
                    Good hostGood = goods[good.q];
                    if (hostGood.extraIndex1 == -1) {
                        hostGood.extraIndex1 = i;
                    } else {
                        hostGood.extraIndex2 = i;
                    }
                }
            }

            int[][] dp = new int[goodCount + 1][money + 1];

            for (int i = 1; i <= goodCount; i++) {
                Good good = goods[i];
                for (int j = 10; j <= money; j += 10) {
                    dp[i][j] = dp[i - 1][j];
                    //当前是附件或者价格大于j，则不选
                    if (good.q != 0 || j < good.v) continue;
                    //只选主件
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - good.v] + (good.v * good.p));

                    if (good.extraIndex1 != -1) {
                        //选主件和附件1
                        Good extra1 = goods[good.extraIndex1];
                        if (j >= good.v + extra1.v) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (good.v + extra1.v)] + (good.v * good.p) + (extra1.v * extra1.p));
                        }

                        if (good.extraIndex2 != -1) {
                            //选主件和附件2
                            Good extra2 = goods[good.extraIndex2];
                            if (j >= good.v + extra2.v) {
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (good.v + extra2.v)] + (good.v * good.p) + (extra2.v * extra2.p));
                            }

                            //选主件和附件1和2
                            if (j >= good.v + extra1.v + extra2.v) {
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - (good.v + extra1.v + extra2.v)] + (good.v * good.p) + (extra1.v * extra1.p) + (extra2.v * extra2.p));
                            }
                        }
                    }
                }
            }
            System.out.println(dp[goodCount][money]);
        }
    }

    static class Good {
        final int v;
        final int p;
        final int q;

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

        int extraIndex1 = -1;
        int extraIndex2 = -1;
    }
}