题解 | #购物单#

import java.util.*;

public class Main {
    private static final int STEP = 10;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int M = in.nextInt() / STEP;
            int N = in.nextInt();

            int[][] w = new int[N + 1][3];
            int[][] v = new int[N + 1][3];
            for (int i = 1; i <= N; ++i) {
                int cost = in.nextInt();
                int ratio = in.nextInt();
                int acc = in.nextInt();
                if (acc == 0) {
                    w[i][0] = cost / STEP;
                    v[i][0] = cost * ratio;
                } else {
                    if (w[acc][1] == 0) {
                        w[acc][1] = cost / STEP;
                        v[acc][1] = cost * ratio;
                    } else {
                        w[acc][2] = cost / STEP;
                        v[acc][2] = cost * ratio;
                    }
                }
            }

            // 参数初始化完毕
            int[][] dp = new int[N + 1][M + 1];
            // base case 初始化完毕
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= M; ++j) {
                    dp[i][j] = dp[i - 1][j]; // 钱不够肯定是不能选择的
                    if (j >= w[i][0]) // 选择了主件
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i][0]] + v[i][0]);
                    if (j >= w[i][0] + w[i][1])
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i][0] - w[i][1]] + v[i][0] + v[i][1]);
                    if (j >= w[i][0] + w[i][2])
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i][0] - w[i][2]] + v[i][0] + v[i][2]);
                    if (j >= w[i][0] + w[i][1] + w[i][2])
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i][0] - w[i][1] - w[i][2]] + v[i][0] + v[i][1] + v[i][2]);
                }
            }

            System.out.println(dp[N][M]);
        }
        in.close();
    }
}