题解 | 购物单

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int totalMoney = sc.nextInt() / 10, n = sc.nextInt();
        Good[] goods = new Good[n + 1];
        for(int i = 1; i <= n; i++){
            int price = sc.nextInt() / 10;
            int importance = sc.nextInt();
            int id = sc.nextInt();
            goods[i] = new Good(price, importance, id);
        }
        for(int i = 1; i <= n; i++){
            int id = goods[i].id;
            if(id > 0){
                if(goods[id].id1 == 0){
                    goods[id].setId1(i);
                }else{
                    goods[id].setId2(i);
                }
            }
        }
        // for(int i = 1; i <= n; i++){
        //     System.out.println(goods[i].price + " " + goods[i].importance + " " + goods[i].id + " " + goods[i].id1 + " " + goods[i].id2);
        // }
        int[][] f = new int[n + 1][totalMoney + 1];
        for(int i = 1; i <= n; i++){
            int price = goods[i].price;
            int price1 = 0, price2 = 0, price3 = 0;
            int x = goods[i].importance * price;
            int y = 0, z = 0, k = 0;
            if(goods[i].id1 != 0){
                price1 = goods[goods[i].id1].price + price;
                y = x + goods[goods[i].id1].price * goods[goods[i].id1].importance;
            }
            if(goods[i].id2 != 0){
                price2 = goods[goods[i].id2].price + price;
                z = x + goods[goods[i].id2].price * goods[goods[i].id2].importance;
            }
            if(goods[i].id1 != 0 && goods[i].id2 != 0){
                price3 = price1 + price2 - price;
                k = y + z - x;
            }
            for(int j = 1; j <= totalMoney; j++){
                f[i][j] = f[i - 1][j];
                if(goods[i].id == 0) {
                    f[i][j] = f[i - 1][j];
                    if(j >= price && price != 0) f[i][j] = Math.max(f[i][j], f[i - 1][j - price] + x);
                    if(j >= price1 && price1 != 0) f[i][j] = Math.max(f[i][j], f[i - 1][j - price1] + y);
                    if(j >= price2 && price2 != 0) f[i][j] = Math.max(f[i][j], f[i - 1][j - price2] + z);
                    if(j >= price3 && price3 != 0) f[i][j] = Math.max(f[i][j], f[i - 1][j - price3] + k);
                }
            }
        }
        System.out.println(f[n][totalMoney] * 10);
    }
}

class Good{
    int price;
    int importance;
    int id;
    int id1;
    int id2;
    public Good(int price, int importance, int id){
        this.price = price;
        this.importance = importance;
        this.id = id;
    }

    public void setId1(int id1){
        this.id1 = id1;
    }

    public void setId2(int id2){
        this.id2 = id2;
    }
}