题解 | 购物单

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            // int a = in.nextInt();
            // int b = in.nextInt();
            // System.out.println(a + b);

            int n = in.nextInt();
            int m = in.nextInt();
            n /= 10;

            // 价格数组，从第1行开始
            // 每行第一列为物品价格/10
            // 第二列为附件1价格/10
            // 第三列为附件2价格/10
            int[][] ps = new int[m + 1][3];
            // 满意度数组，从第1行开始
            // 每行第一列为物品满意度（价格/10）
            // 第二列为附件1满意度（价格/10）
            // 第三列为附件2满意度（价格/10）
            int[][] ws = new int[m + 1][3];

            for (int i = 1; i <= m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                int c = in.nextInt();
                a /= 10;
                b = b * a;
                if (c == 0) {
                    // 物品
                    ps[i][0] = a;
                    ws[i][0] = b;
                } else {
                    if (ps[c][1] == 0) {
                        // 附件1
                        ps[c][1] = a;
                        ws[c][1] = b;
                    } else {
                        // 附件2
                        ps[c][2] = a;
                        ws[c][2] = b;
                    }
                }
            }

            int[][] arr = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                int a = ps[i][0];
                int b = ws[i][0];
                int c = ps[i][1];
                int d = ws[i][1];
                int e = ps[i][2];
                int f = ws[i][2];
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = j >= a ? Math.max(arr[i - 1][j], arr[i - 1][j - a] + b) : arr[i - 1][j];
                    arr[i][j] = j >= (a + c) ? Math.max(arr[i][j], arr[i - 1][j - a - c] + b + d) : arr[i][j];
                    arr[i][j] = j >= (a + e) ? Math.max(arr[i][j], arr[i - 1][j - a - e] + b + f) : arr[i][j];
                    arr[i][j] = j >= (a + c + e) ? Math.max(arr[i][j], arr[i - 1][j - a - c - e] + b + d + f) : arr[i][j];
                }
            }

            System.out.println(arr[m][n]*10);
        }
    }
}