题解 | #购物单#d

import java.util.Scanner;
//100%样例通过
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int remainMoney = in.nextInt();
        int num = in.nextInt();
        Good[] g = new Good[num+1];
		
	  	//这里和之前参考的老哥第一个不同之处在于一定要先初始化，否则有一个样例通不过。
	  //原因是因为那个样例附件在主件前面出现
        for(int i = 1;i<=num;i++){
            g[i] = new Good(0,0,0);

        }


        for(int i = 1;i<=num;i++){
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();
		  	//赋值操作
            g[i].v = v; g[i].p = p; g[i].q = q;

            if(q>0){//物品的主附件ID
                if(g[q].a1 == 0)
                g[q].setA1(i);  //设置主件的附件为当前附件
                else g[q].setA2(i);
            }
        }

        int [][]dp = new int[num+1][remainMoney+1];
        for(int i =1;i<=num;i++){
            int v = 0,v1 = 0,v2 = 0,v3 = 0,tempdp = 0,tempdp1=0,tempdp2 = 0,tempdp3 = 0;
            v = g[i].v;
            tempdp = g[i].p * v; //只有主件

            if(g[i].a1 != 0){  //主件加附件1
                v1 = g[g[i].a1].v + v;
                tempdp1 = tempdp + g[g[i].a1].v * g[g[i].a1].p;
            }
            if(g[i].a2 != 0){ //主件加附件2
                v2 = g[g[i].a2].v + v;
                tempdp2 = tempdp + g[g[i].a2].v * g[g[i].a2].p;
            }

            if(g[i].a1!=0 && g[i].a2!=0){  //主件加附件1加附件2
                v3 = g[g[i].a1].v + g[g[i].a2].v + v;
                tempdp3 = tempdp + g[g[i].a2].v * g[g[i].a2].p + g[g[i].a1].v * g[g[i].a1].p;
            }
            for(int j =1;j<=remainMoney;j++){
                if(g[i].q>0){  //当物品i是附件时，相当于跳过
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j];  //不购买当前主件
                    if(j>=v && v!= 0) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v] + tempdp);
                    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);
                }
            }

        }
        System.out.println(dp[num][remainMoney]);

    }

    /**
    定义物品类
     */

     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(){}

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

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


     }
}