题解 | #购物单#

import java.util.*;

/** 
 * 重点是，dp[i][j]取值时考虑的几种情形，
 * 1.不要当前主件，2.只要当前主件，3.主件+附件1，4.主件+附件2，5.主件+附件1+附件2
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int sum = in.nextInt();
            int len = in.nextInt();
            List<NodeObject> masters = new ArrayList<>();
            Map<Integer, List<NodeObject>> annexs = new HashMap<>();
            for (int i = 0; i < len; i++) {
                int p = in.nextInt();
                int w = in.nextInt();
                // 主件id，-1代表自身是主件
                int f = in.nextInt() - 1;
                NodeObject nodeObject = new NodeObject();
                nodeObject.id = i;
                nodeObject.p = p;
                nodeObject.w = w;
                if (f == -1) {
                    // 主件放入masters
                    masters.add(nodeObject);
                } else {
                    List<NodeObject> defaultList = new ArrayList<>();
                    List<NodeObject> list = annexs.getOrDefault(f, defaultList);
                    list.add(nodeObject);
                    // 附件放入annexs
                    annexs.put(f, list);
                }
            }
            // dp[i][j] 代表前0~i件物品，不超过j金额，可以获得的最大满意度
            int[][] dp = new int[masters.size() + 1][sum + 1];
            for (int i = 1; i < masters.size() + 1; i++) { 
                for (int j = 0; j < sum + 1; j++) {
                    NodeObject master = masters.get(i - 1);
                    if (j - master.p >= 0) {
                        // 先考虑主件，不要主件/只要主件
                        // masterV主件带来的满意度
                        int masterV = master.p * master.w;
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - master.p] + masterV);
                        // 再考虑附件,最多2个附件
                        List<NodeObject> defaultList = new ArrayList<>();
                        List<NodeObject> annexList = annexs.getOrDefault(master.id, defaultList);
                        // 主件+1个附件
                        for (int k = 0; k < annexList.size(); k++) {
                            int p = j - master.p - annexList.get(k).p;
                            if (p >= 0) {
                                // 附件带来的满意度
                                int v = annexList.get(k).p * annexList.get(k).w;
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][p] + masterV + v);
                            }
                        }
                        // 主件+2个附件
                        if (annexList.size() == 2) {
                            int p = j - master.p - annexList.get(0).p - annexList.get(1).p;
                            if (p >= 0) {
                                int v2 = annexList.get(1).p * annexList.get(1).w;
                                int v1 = annexList.get(0).p * annexList.get(0).w;
                                int dpI = dp[i - 1][p] + masterV + v1 + v2;
                                dp[i][j] = Math.max(dp[i][j], dpI);
                            }
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            System.out.println(dp[masters.size()][sum]);
        }
    }
    static class NodeObject {
        int id;
        int p;
        int w;
    }
}