题解 | #购物单#

public class Main {
  public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int N = sc.nextInt();    //预算的钱
            int m = sc.nextInt();       //数量
            N /= 10;
            int[][] price = new int[m + 1][3];
            int[][] weight = new int[m + 1][3];
            for (int i = 1; i <= m; i++) {
                int v = sc.nextInt();
                int p = sc.nextInt();
                int q = sc.nextInt();
                v /= 10;
                p = p * v;
                if (q == 0) {
                    price[i][0] = v;
                    weight[i][0] = p;
                } else if (price[q][1] == 0) {
                    price[q][1] = v;
                    weight[q][1] = p;
                } else {
                    price[q][2] = v;
                    weight[q][2] = p;
                }
            }
            int[][] ans = new int[m + 1][N + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= N; j++) {
                    int a = price[i][0];
                    int b = price[i][1];
                    int c = price[i][2];
                    int wa = weight[i][0];
                    int wb = weight[i][1];
                    int wc = weight[i][2];
                    ans[i][j] = j - a >= 0 ? Math.max(ans[i-1][j], ans[i - 1][j - a] + wa) : ans[i - 1][j];
                    ans[i][j] = j - a - b >= 0 ? Math.max(ans[i][j], ans[i - 1][j - a - b] + wb + wa) : ans[i][j];
                    ans[i][j] = j - a - c >= 0 ? Math.max(ans[i][j], ans[i - 1][j - a - c] + wa + wc) : ans[i][j];
                    ans[i][j] = j - a - b - c >= 0 ? Math.max(ans[i][j], ans[i - 1][j - a - b - c] + wa + wc + wb) : ans[i][j];
                }
            }
            System.out.println(ans[m][N] * 10);
            sc.nextLine();
        }
    }
}