题解 | #购物单#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int[][] dpFlag;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt() / 10;  // 总钱数 N<3200
        int m = sc.nextInt();  // 可购买的物品的个数 m <60
        Map<Integer, List<Integer>> data1 = new HashMap<>(); // 0：价格  1：重要度（1-5） 2：主件还是附件
        Map<Integer, List<Integer>> data2 = new HashMap<>(); // 0：价格  1：重要度（1-5） 2：主件还是附件
        for (int i = 0; i < m; i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0; j < 3; j++) {
                if(j == 0){
                    tmp.add(sc.nextInt() / 10);  // 价格都是10的倍数，故除10，减少dpFlag存储空间
                } else {
                    tmp.add(sc.nextInt());
                }
            }
            if (tmp.get(2) == 0) {
                data1.put(i + 1, tmp);
            } else {
                data2.put(i + 1, tmp);
            }
        }
        int ret = gwd(data1, data2, N, m);
        System.out.println(ret * 10);  // 结果要乘10
    }

    private static int gwd(Map<Integer, List<Integer>> data1,
                           Map<Integer, List<Integer>> data2, int N, int m) {
		// 处理数据，主商品放入data1，存在附件，则通过value的的list查找，如果list.size == 3,表示没有附件，list.size == 4,有1个附件，list.size == 5,有2个附件，data2存储附件信息，通过list列表数据进行查找
        for (Integer key : data2.keySet()) {
            int q = data2.get(key).get(2);
            data1.get(q).add(key);
        }
        Set<Integer> tmp = new HashSet<>();
        for (Integer key : data1.keySet()) {
            tmp.add(key);
        }
        for (Integer key1 : tmp) {
            data1.put(key1 + 60, data1.get(key1));
            data1.remove(key1);
        }
        int index = 1;
        tmp.clear();
        for (Integer key : data1.keySet()) {
            tmp.add(key);
        }
        for (Integer key1 : tmp) {
            data1.put(index++, data1.get(key1));
            data1.remove(key1);
        }
        dpFlag = new int[N + 1][data1.size() + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= data1.size(); j++) {
                dpFlag[i][j] = -1;
            }
        }
        return dp(data1, data2, N, data1.size());
    }

    private static int dp(Map<Integer, List<Integer>> data1,
                          Map<Integer, List<Integer>> data2, int N, int m) {
        if (m == 0) {
            return 0;
        } else if (N == 0) {
            return 0;
        }
        if (dpFlag[N][m] != -1) {  // 查找记录，找到记录不再计算
            return dpFlag[N][m];
        }

        List<Integer> zhu = data1.get(m);
        int v1 = 0, v2 = 0, v3 = 0, w1 = 0, w2 = 0, w3 = 0; // 商品价格和重要度
        int b0 = 0, b1 = 0, b21 = 0, b22 = 0, b3 = 0; 
	    // 购买0个商品的最大满意度，只买1个主商品，买主商品和附件1，买主商品和附件2，买主商品和附件1、附件2
        int ret = 0; // 记录计算数据
        b0 = dp(data1, data2, N, m - 1);   // b0计算是任意条件需要的，提到最外处
        if (zhu.size() == 3) { // 该主商品没有附件
            v1 = zhu.get(0);
            w1 = zhu.get(1);
            if (N >= v1) {     // 买的起主商品
                b1 = dp(data1, data2, N - v1, m - 1) + v1 * w1;
                ret = Math.max(b0, b1);
                dpFlag[N][m] = ret;
                return ret;
            } else {           // 买不起
                dpFlag[N][m] = b0;
                return b0;
            }
        } else if (zhu.size() == 4) {  // 该主商品有1个附件
            v1 = zhu.get(0);
            w1 = zhu.get(1);
            v2 = data2.get(zhu.get(3)).get(0);
            w2 = data2.get(zhu.get(3)).get(1);
            if (N >= v1) {            // 分支判断，减少b1重复计算
                b1 = dp(data1, data2, N - v1, m - 1) + v1 * w1;
            }
            if (N >= v1 + v2) {      // 买的起主商品1和唯一附件
                b21 = dp(data1, data2, N - v1 - v2, m - 1) + v1 * w1 + v2 * w2;
                ret = Math.max(Math.max(b0, b1), b21);
                dpFlag[N][m] = ret;
                return ret;
            } else if (N >= v1) {   // 只买的起主商品1
                ret = Math.max(b0, b1);
                dpFlag[N][m] = ret;
                return ret;
            } else {                // 买不起商品
                dpFlag[N][m] = b0;
                return b0;
            }
        } else {
            v1 = zhu.get(0);
            w1 = zhu.get(1);
            v2 = data2.get(zhu.get(3)).get(0);
            w2 = data2.get(zhu.get(3)).get(1);
            v3 = data2.get(zhu.get(4)).get(0);
            w3 = data2.get(zhu.get(4)).get(1);
            if (N >= v1) {            // 计算b1
                b1 = dp(data1, data2, N - v1, m - 1) + v1 * w1;
            }
            if (N >= v1 + v2) {       // 计算b21,即购买主商品和附件1的最大满意度
                b21 = dp(data1, data2, N - v1 - v2, m - 1) + v1 * w1 + v2 * w2;
            }
            if (N >= v1 + v3) {       // 计算b22,即购买主商品和附件2的最大满意度
                b22 = dp(data1, data2, N - v1 - v3, m - 1) + v1 * w1 + v3 * w3;
            }
            if (N >= v1 + v2 + v3) { // 买的起主商品和附件1、附件2
                b3 = dp(data1, data2, N - v1 - v2 - v3, m - 1)
                        + v1 * w1 + v2 * w2 + v3 * w3;  // 计算b3,即购买主商品和附件1和附件2的最大满意度
                ret = Math.max(Math.max(Math.max(b0, b1), Math.max(b21, b22)), b3);
                dpFlag[N][m] = ret;
                return ret;
            } else if (N >= v1 + v2 || N >= v1 + v3) { // 买的起主商品以及（附件1或附件2）
                ret = Math.max(Math.max(b0, b1), Math.max(b21, b22));
                dpFlag[N][m] = ret;
                return ret;
            } else if (N >= v1) {   // 只买的起附件1
                ret = Math.max(b0, b1);
                dpFlag[N][m] = ret;
                return ret;
            } else {               // 都买不起
                dpFlag[N][m] = b0;
                return b0;
            }
        }
    }
}