题解 | #购物单#

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int m = scanner.nextInt();
    Good[] goods = new Good[m + 1];
    for (int i = 1; i < m + 1; i++) {
        int j = scanner.nextInt();
        int p = scanner.nextInt();
        int q = scanner.nextInt();
        goods[i] = new Good(j, p, q);
    }
    //不在上个循环里添加附件为了避免空指针
    for (int i = 1; i < m + 1; i++){
        int q =goods[i].q;
        if (q > 0) {
            if (goods[q].a1 == 0) {
                goods[q].setA1(i);
            } else {
                goods[q].setA2(i);
            }
        }
    }
    compareAndPrint(N,goods);

}

public static int max(int a, int b) {
    return a > b ? a : b;
}

public static void compareAndPrint(int n, Good[] goods) {
    int[][] res=new int[goods.length][n+1];
    for (int i=1;i< goods.length;i++){
        int j=-1,j1=-1,j2=-1,j3=-1,dg=-1,dg1=-1,dg2=-1,dg3=-1;
        //不带附件的满意度和价格
        j=goods[i].j;
        dg=goods[i].j*goods[i].p;
        //带附件1的满意度和价格
        if (goods[i].a1!=0){
            j1=goods[i].j+goods[goods[i].a1].j;
            dg1=goods[i].j*goods[i].p + goods[goods[i].a1].j * goods[goods[i].a1].p;
        }
        //只带附件2的满意度和价格
        if (goods[i].a2!=0){
            j2=goods[i].j+goods[goods[i].a2].j;
            dg2=goods[i].j*goods[i].p + goods[goods[i].a2].j * goods[goods[i].a2].p;
        }
        //两个附件加主件的满意度和价格
        if (goods[i].a1!=0 && goods[i].a2!=0){
            j3=goods[i].j+goods[goods[i].a1].j+goods[goods[i].a2].j;
            dg3=goods[i].j*goods[i].p + goods[goods[i].a1].j * goods[goods[i].a1].p + goods[goods[i].a2].j * goods[goods[i].a2].p;
        }
        for (int m=1;m<n+1;m++){
            res[i][m]=res[i-1][m];
            if (goods[i].q!=0){
                continue;
            }else {
                int temp=0;
                if (m>=j && j!=-1){
                    //  a:不带这个物品时 m块钱能买到的最高满意度
                    //b:不带这个物品时用剩余金额(m-当前物品价格)买到的最高满意度+这个物品的满意度   
                    //a b比较取大值
                    temp = max(max(res[i-1][m],res[i-1][m-j]+dg),temp);
                }
                if (m>=j1 && j1!=-1){
                    temp = max(max(res[i-1][m],res[i-1][m-j1]+dg1),temp);
                }
                if (m>=j2 && j2!=-1){
                    temp = max(max(res[i-1][m],res[i-1][m-j2]+dg2),temp);
                }
                if (m>=j3 && j3!=-1){
                    temp = max(max(res[i-1][m],res[i-1][m-j3]+dg3),temp);
                }
                res[i][m] = max(res[i][m],temp);
            }
        }
    }
    System.out.println(res[goods.length-1][n]);

}

static class Good {
    //价格
    public int j;

    //重要度
    public int p;

    //主附件
    public int q;

    //附件物品编号
    public int a1;

    public int a2;

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

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

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

}