题解 | 购物单

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // Budget
        int m = scanner.nextInt(); // Total number of items
        n /= 10; // Since all prices are multiples of 10, we can scale down

        List<List<Item>> groups = new ArrayList<>();
        Item[] items = new Item[m + 1]; // Items are 1-based indexed

        for (int i = 1; i <= m; i++) {
            int v = scanner.nextInt() / 10;
            int w = scanner.nextInt();
            int q = scanner.nextInt();
            items[i] = new Item(v, w, q);
            if (q == 0) {
                List<Item> group = new ArrayList<>();
                group.add(items[i]);
                groups.add(group);
            }
        }

        // Process attachments and add them to their respective main items
        for (int i = 1; i <= m; i++) {
            if (items[i].q > 0) {
                Item mainItem = items[items[i].q];
                for (List<Item> group : groups) {
                    if (group.get(0) == mainItem) {
                        if (group.size() < 3) { // A main item can have at most two attachments
                            group.add(items[i]);
                        }
                        break;
                    }
                }
            }
        }

        int[] dp = new int[n + 1];

        for (List<Item> group : groups) {
            Item main = group.get(0);
            int v = main.v;
            int w = main.v * main.w;

            // Collect all possible combinations of the main item and its attachments
            List<int[]> combinations = new ArrayList<>();
            combinations.add(new int[]{v, w});

            if (group.size() > 1) {
                Item a1 = group.get(1);
                combinations.add(new int[]{v + a1.v, w + a1.v * a1.w});
                if (group.size() > 2) {
                    Item a2 = group.get(2);
                    combinations.add(new int[]{v + a2.v, w + a2.v * a2.w});
                    combinations.add(new int[]{v + a1.v + a2.v, w + a1.v * a1.w + a2.v * a2.w});
                }
            }

            // Update the dp array by considering each combination
            for (int i = n; i >= 0; i--) {
                for (int[] combo : combinations) {
                    int cost = combo[0];
                    int value = combo[1];
                    if (i >= cost) {
                        dp[i] = Math.max(dp[i], dp[i - cost] + value);
                    }
                }
            }
        }

        System.out.println(dp[n] * 10); // Scale back up the result
    }

    static class Item {
        int v; // Price (scaled down by 10)
        int w; // Importance
        int q; // Main item ID (0 if it's a main item)

        Item(int v, int w, int q) {
            this.v = v;
            this.w = w;
            this.q = q;
        }
    }
}