题解 | #购物单#参考题解

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
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);

        good[] gs = new good[n+1];
        for (int  i=1;i<=n;i++){
            int v = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            good gd = new good(v, p, q);
            gs[i] = gd;
        }
        
        for (int  i=1;i<=n;i++){
            good gd = gs[i];
            //如果是附件
            if(gd.q>0){
                //设置主件的附件id
                if(gs[gd.q].a1==0){
                    gs[gd.q].setA1(i);
                }else {
                    gs[gd.q].setA2(i);
                }
            }
        }

        //二维数组
        int[][] dp = new int[n+1][money +1 ];
        for (int i=1 ;i<=n;i++){
            int v=0, v1=0, v2=0, v3=0, temp=0, temp1=0, temp2=0, temp3 = 0;
            //只有主键的价格和满意度
            good g = gs[i];
            v = g.v;
            temp = v * g.p;

            //主键 和附件1
            if(g.a1>0){
                v1 = gs[g.a1].v + v;
                temp1 = temp + gs[g.a1].v * gs[g.a1].p;
            }
            if(g.a2>0){
                v2 = gs[g.a2].v + v;
                temp2 = temp + gs[g.a2].v * gs[g.a2].p;
            }
            if(g.a1>0&&g.a2>0){
                v3 = gs[g.a2].v+gs[g.a1].v + v;
                temp3 = temp + gs[g.a1].v * gs[g.a1].p+gs[g.a2].v * gs[g.a2].p;
            }
            for (int j=1;j<=money;j++){
                //当是附件时直接跳过
                if(g.q>0){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i - 1][j];
                    if(j>=v&v!=0){
                        dp[i][j] = Integer.max(dp[i][j], dp[i - 1][j - v] + temp);
                    }
                     if(j>=v1&v1!=0){
                        dp[i][j] = Integer.max(dp[i][j], dp[i - 1][j - v1] + temp1);
                     }
                    if(j>=v2&v2!=0){
                        dp[i][j] = Integer.max(dp[i][j], dp[i - 1][j - v2] + temp2);
                    }
                    if(j>=v3&v3!=0){
                        dp[i][j] = Integer.max(dp[i][j], dp[i - 1][j - v3] + temp3);
                    }
                }

            }

        }
        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;
        }
    }
}