题解 | 购物单

此题解使用了BufferedReader + StreamTokenizer + PrintWriter提高了IO速度，通过封装函数将核心算法抽象出来。

import java.io.*;

public class Main {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out))) {
            StreamTokenizer in = new StreamTokenizer(br);
            while (in.nextToken() != StreamTokenizer.TT_EOF) {
                int m = (int) in.nval;
                in.nextToken();
                int n = (int) in.nval;
                Good[] allGoods = new Good[n];
                int primaryCount = 0;
                for (int i = 0; i < n; i++) {
                    allGoods[i] = readGood(in);
                    if (allGoods[i].q == 0) {
                        primaryCount++;
                    }
                }
                Good[] primaryGoods = new Good[primaryCount];
                int primaryIndex = 0;
                for (Good good : allGoods) {
                    if (good.q == 0) {
                        primaryGoods[primaryIndex++] = good;
                    } else {
                        allGoods[good.q - 1].appendix(good);
                    }
                }
                out.println(solution(primaryGoods, m));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static Good readGood(StreamTokenizer in) throws IOException {
        in.nextToken();
        int v = (int) in.nval;
        in.nextToken();
        int w = (int) in.nval;
        in.nextToken();
        int q = (int) in.nval;
        return new Good(v, w, q);
    }

    public static int solution(Good[] primary, int m) {
        int[][] dp = new int[m + 1][primary.length];
        for (int j = 0; j < primary.length; j++) {
            Good cur = primary[j];
            for (int i = 1; i <= m; i++) {
                int best = j > 0 ? dp[i][j - 1] : 0;
                int[] values = cur.getAllValue();
                int[] joys = cur.getAllJoy();
                for (int k = 0; k < cur.size; k++) {
                    if (i - values[k] >= 0) {
                        best = Math.max(best, joys[k] + (j > 0 ? dp[i - values[k]][j - 1] : 0));
                    }
                }
                dp[i][j] = best;
            }
        }
        return primary.length > 0 ? dp[m][primary.length - 1] : 0;
    }

    private static class Good {
        public int v;
        public int w;
        public int q;
        public int size = 1;
        public Good a1 = null;
        public Good a2 = null;

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

        public void appendix(Good a) {
            if (a1 == null) {
                a1 = a;
                size++;
            } else {
                a2 = a;
                size += 2;
            }
        }

        public int[] getAllValue() {
            int[] result = new int[size];
            result[0] = v;
            if (a1 != null) {
                result[1] = v + a1.v;
            }
            if (a2 != null) {
                result[2] = v + a2.v;
                result[3] = v + a1.v + a2.v;
            }
            return result;
        }

        public int[] getAllJoy() {
            int[] result = new int[size];
            result[0] = v * w;
            if (a1 != null) {
                result[1] = v * w + a1.v * a1.w;
            }
            if (a2 != null) {
                result[2] = v * w + a2.v * a2.w;
                result[3] = v * w + a1.v * a1.w + a2.v * a2.w;
            }
            return result;
        }
    }
}