题目描述

帕特尔博士有N 堆盘子。

每堆恰好有包含K个盘子。

每个盘子都有一个正的美丽值，用来描述它的美观程度。

帕特尔博士想拿P个盘子用于今晚的晚宴。

如果他想拿走一堆中的某个盘子，那么他还需要将该堆盘子中堆叠在该盘子上面的所有盘子一起拿走。

请帮助帕特尔博士挑选盘子，使得所选盘子的美丽值之和尽可能大。

输入格式

第一行包含整数T，表示共有T组测试数据。

对于每组数据，第一行包含三个整数 N,K,P。

接下来 N行，每行包含K个整数，描述一个盘子堆中，从顶到底每个盘子的美丽值。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: y，其中x为组别编号（从 1 开始），y 为所选盘子的美丽值之和的最大可能值。

数据范围

$ 1 \leq T \leq 100 $,
$ 1 \leq K \leq 30 $,
$ 1 \leq P \leq N×K $，
$ 1 \leq N \leq 50 $,
每个盘子的美丽值范围[1,100]。

样例

输入样例：

2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

输出样例：

Case #1: 250
Case #2: 180

算法1

(动态规划) $O(NPK)$

我们设f[i][j] 为选了i堆，选了j个盘子的方案集合
目标就是寻找最大美丽值：

分为一下两个方面：

• 不从i堆里选：f[i][j]不变。

• 选：

  • 这时候要枚举从i堆选几个，设选l个
  • 则状态转移方程为：
  • f[i][j] = f[i - 1][j - l] + sum[i][l]
  • 其中sum[i][l] 表示从i堆选了l个的美丽值，我们可以预处理前缀和求得

时间复杂度

动态规划三重循环，$O(NPK)$

参考文献

GoogleKickstart官网

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 55, M = 35;

int n, k, p;
int a[N][M];
int sum[N][M];
int f[N][N * M];

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T--){
        cin >> n >> k >> p;
        memset(sum, 0, sizeof sum);
        memset(f, 0, sizeof f);

        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= k; j ++){
                cin >> a[i][j];
            }
        }

        for(int i = 1; i <= n; i++){
            sum[i][1] = a[i][1];
            for(int j = 2; j <= k; j++){
                sum[i][j] = sum[i][j - 1] + a[i][j];
            }
        }

        for(int i = 1; i <= k; i ++) f[1][i] = sum[1][i];
        for(int i = 2; i <= n; i ++){
            for(int j = 0; j <= p; j ++){
                if(j > i * k) break;
                for(int l = 0; l <= k; l ++){
                    if(j >= l) f[i][j] = max(f[i][j], f[i - 1][j - l] + sum[i][l]);
                }
            }
        }

        printf("Case #%d: %d\n",cnt++, f[n][p]);
    }
    return 0;
}