Description

这里有一个 \(n \times m\) 的矩阵, 请你选出其中 \(k\) 个子矩阵, 使得这个 \(k\) 个子矩阵 分值之和最大. 注意: 选出的 \(k\) 个子矩阵不能相互重叠.

Input

第一行为 \(n, m, k (1 \leq n \leq 100, 1 \leq m \leq 2, 1 \leq k \leq 10)\), 接下 来 \(n\) 行描述矩阵每行中的每个元素的分值 (每个元素的分值的绝对值不超过 \(32767\)) .

Output

只有一行为 \(k\) 个子矩阵分值之和最大为多少.

Sample Input

3 2 2
1 -3
2 3
-2 3

Sample Output

9

Explanation

首先根据出题人的节操保证子矩阵分值之和不会爆 long long, 然后可以放心地用 int

研究一下可以发现幸好 \(m \leq 2\), 不然这道题基本没法做 (至少我这样的蒟蒻不会). 大概分析一下可以认为每一行上选了那些等等, 然后空间复杂度应该是 \(O(n^m \cdot k)\), 然后会有一个比较可怕的时间复杂度 \(O(n^m \cdot 2^m \cdot k)\), 但是因为这里的 \(m\) 比较 (很) 小, 所以那一堆 NP 的玩意儿可以暂行忽略~

最后水一发 DP 就可以了. 不过本人为了代码的美观度加了一堆 define, 诸位大神们就 凑合看吧......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define maximize(__x,__y) __x=max(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 110, maxk = 12;

int n, m, K;
int arr[3][maxn];
int dp_1d[maxn][maxk],
    dp_2d[maxn][maxn][maxk];
int sum_1d[maxn],
    sum_2d[2][maxn];
int res;

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &K);
    if (m == 1) { // 1 dimension rows
        #define sum(__x) sum_1d[__x]
        #define dp(__x,__y) dp_1d[__x][__y]
        for (int i = 1; i <= n; i++) {
            scanf("%d", &arr[1][i]);
            sum(i) = sum(i - 1) + arr[1][i];
        }
        for (int i = 1; i <= n; i++)
            for (int k = 1; k <= K; k++) {
                dp(i, k) = dp(i - 1, k);
                for (int j = 0; j < i; j++)
                    dp(i, k) = max(dp(i, k), dp(j, k - 1) + sum(i) - sum(j));
            }
        res = dp(n, K);
        #undef sum
        #undef dp
    } else if (m == 2) { // 2 dimension rows
        #define sum(__x,__y) sum_2d[__x][__y]
        #define dp(__x,__y,__z) dp_2d[__x][__y][__z]
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &arr[1][i], &arr[2][i]);
            sum(1, i) = sum(1, i - 1) + arr[1][i];
            sum(2, i) = sum(2, i - 1) + arr[2][i];
        }
        for (int k = 1; k <= K; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) {
                    // dp(i, j, k) = upper row @ i, lower row @ j, selected k matrices
                    dp(i, j, k) = max(dp(i - 1, j, k), dp(i, j - 1, k));
                    for (int l = 0; l < i; l++)
                        maximize(dp(i, j, k), dp(l, j, k - 1) + sum(1, i) - sum(1, l));
                    for (int l = 0; l < j; l++)
                        maximize(dp(i, j, k), dp(i, l, k - 1) + sum(2, j) - sum(2, l));
                    if (i == j) for (int l = 0; l < i; l++) // Same position
                        maximize(dp(i, j, k), dp(l, l, k - 1) + sum(1, i) - sum(1, l) + sum(2, j) - sum(2, l));
                }
        res = dp(n, n, K);
        #undef sum
        #undef dp
    }
    printf("%d\n", res);
    return 0;
}