题解 | #购物单#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            long s = System.currentTimeMillis();
            String line1 = in.nextLine();
            String[] arr = line1.split(" ");
            int money = Integer.parseInt(arr[0]);
            int count = Integer.parseInt(arr[1]);
            List list = new ArrayList<>();//主件容器
            Map<Integer, List<String[]>> map = new HashMap<>();//副件容器
            while (count > 0) {
                String[] items = in.nextLine().split(" ");
                int type = Integer.parseInt(items[2]);
                if (type > 0) {//保存副件
                    if (!map.containsKey(type)) {
                        map.put(type, new ArrayList<String[]>());
                    }
                    map.get(type).add(items);
                    list.add(null);//占位置
                } else {//保存主件
                    list.add(items);
                }
                count--;
            }
            int v = visit(money, list, map);
            System.out.println(v);
        }
    }
    
    private static int visit(int c, List<String[]> list, Map<Integer, List<String[]>> map) {//动态规划dp
        int n = list.size();

        int[] dp = new int[c + 1];
        for (int i = 0; i < n; i++) {
            if (list.get(i) == null) continue;

            int w = Integer.parseInt(list.get(i)[0]);
            int v = Integer.parseInt(list.get(i)[0]) * Integer.parseInt(list.get(i)[1]);
            for (int j = c; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
                if (map.containsKey(i + 1)) {
                    List<String[]> app = map.get(i + 1);
                    if (app.size() > 0) {//计算第一个副件
                        int w1 = Integer.parseInt(app.get(0)[0]);
                        int v1 = Integer.parseInt(app.get(0)[0]) * Integer.parseInt(app.get(0)[1]);
                        if (j >= w + w1) {//单选副件1
                            dp[j] = Math.max(dp[j], dp[j - w - w1] + v + v1);
                        }
                    }
                    if (app.size() > 1) {//计算第二个副件
                        int w1 = Integer.parseInt(app.get(0)[0]);
                        int v1 = Integer.parseInt(app.get(0)[0]) * Integer.parseInt(app.get(0)[1]);
                        int w2 = Integer.parseInt(app.get(1)[0]);
                        int v2 = Integer.parseInt(app.get(1)[0]) * Integer.parseInt(app.get(1)[1]);
                        if (j >= w + w2) {//单选副件2
                            dp[j] = Math.max(dp[j], dp[j - w - w2] + v + v2);
                        }
                        if (j >= w + w1 + w2) {//副件1+副件2
                            dp[j] = Math.max(dp[j], dp[j - w - w1 - w2] + v + v1 + v2);
                        }
                    }
                }
            }
        }
        return dp[c];
    }

}