题目

有个藏宝架有n层，每层的宝物数量不一，每个宝物都有其价值，现在要求拿出m个宝物，并且需要遵守规则：

1. 每次只能拿选定层的两端的宝物
2. 要拿出的m个宝物的总价值是各种方案里最大的

输入：（第一行是 n 和 m，后面每一行是各层的数据）
n m
下面每行代表每层，且第一个数是这层宝物的数量k，后面的则是k个宝物的价值
4 1 2 4 5
5 1 2 4 5 5

样例：
2 3
2 3 2
4 1 4 1 5
输出：5+3+2=10
（注意，每一层中，给出的宝物的价值不是排好序的）

方法一 多重背包

比较经典的解法是用多重背包。如果不了解这个算法，可以先康康：https://www.kancloud.cn/kancloud/pack/70127

processValues(int[] values) 输入为每一层的k个宝物的价值，返回的是从这一层中，取0个 - k 个宝物时，可获取的最大价值。

主函数中，先读数据，然后调用processValues() 处理每一层的值，存到 goods 矩阵中，最后进行动态规划。

dp[ i ][ j ] 表示从 0 - i层，取了j 个货物时获取的价值。
状态转移方程为：
（假设第 i 层的货物数量为 length；注意下面方程中的 k 只是一个循环变量）

dp[i][j] = max( { 1 <= k <= min(length, j) | dp[i - 1][j - k] + goods[i][k] } )

这里的 k 其实表示的是在 i 层取了 k 件物品，然后在 （i - 1）层取 （ j - k ）件，加起来就是 j 件。

时间复杂度是 O(nmk)

public class bao_wu_7_27_dp {

    // 对每层的货物，取 0 到 k 个时的最大价值
    // values 是某层货物的价值
    // 比如，temp[0] 为取0个时的最大价值，temp[2]为取2个时的最大价值
    public static int[] processValues(int[] values) {
        int[] temp = new int[values.length + 1];
        temp[0] = 0;
        int i = 0;
        int j = values.length - 1;
        int cur = 1;
        while(cur < temp.length) {
            if (values[i] > values[j]) {
                temp[cur] = values[i] + temp[cur - 1];
                i++;
            } else {
                temp[cur] = values[j] + temp[cur - 1];
                j--;
            }
            cur++;
        }
        return temp;

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 对每层的货物，取 0 到 k 个时的最大价值
        int[][] goods = new int[n][];

        for (int i = 0; i < n; i++) {
            int k = scanner.nextInt();
            int[] values = new int[k];
            for (int j = 0; j < k; j++) {
                values[j] = scanner.nextInt();
            }
            goods[i] = processValues(values);
        }

        int[][] dp = new int[n][m + 1];
        for (int j = 1; j < dp[0].length; j++) {
            if (j < goods[0].length) {
                dp[0][j] = goods[0][j];
            } else {
                break;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                int tmp = dp[i - 1][j];
                for (int k = 1; k <= j; k++) {
                    if (k < goods[i].length) {
                        tmp = Math.max(tmp, dp[i - 1][j - k] + goods[i][k]);
                    }
                }

                dp[i][j] = tmp;
            }
        }
        System.out.println(dp[n - 1][m]);
    }
}

方法二 堆

由于题目的特殊形，这一题不一定要用到动态规划。
可以从大根堆，维护当前可以取到的最大价值的货物，范围为所有层。
依次取出 m 个货物就可以了。

具体：
将每一层的货物价值放入一个双端队列，然后将这 n 个双端队列放入一个大根堆，以每个队列头尾两个元素的最大值作为比较。

时间复杂度为 O(m * log n)

public class bao_wu_7_27_heap {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n  = scanner.nextInt();
        int m = scanner.nextInt();
        PriorityQueue<Deque<Integer>> heap = new PriorityQueue<>((a, b) -> {
            int maxA = Math.max(a.peekFirst(), a.peekLast());
            int maxB = Math.max(b.peekFirst(), b.peekLast());
            return maxB - maxA;
        });

        // 初始化
        for (int i = 0; i < n; i++) {
            Deque<Integer> deque = new LinkedList<>();
            int k = scanner.nextInt();
            for (int j = 0; j < k; j++) {
                deque.addLast(scanner.nextInt());
            }
            heap.add(deque);
        }

        int result = 0;
        for (int i = 0; i < m; i++) {
            Deque<Integer> deque = heap.poll();
            int max = Math.max(deque.peekFirst(), deque.peekLast());
            if (max == deque.peekFirst()) {
                deque.removeFirst();
            } else {
                deque.removeLast();
            }
            result += max;

            if(!deque.isEmpty()){
                heap.add(deque);
            }
        }
        System.out.println(result);
    }
}