题目地址：洛谷：【P2331】[SCOI2005]最大子矩阵 – 洛谷、BZOJ：Problem 1084. — [SCOI2005]最大子矩阵

题目描述

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

输入输出格式

输入格式：
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

输出格式：
只有一行为k个子矩阵分值之和最大为多少。

输入输出样例

输入样例#1：

3 2 2
1 -3
2 3
-2 3

输出样例#1：

9

题解

我们注意到m的范围只有2，不如先想一下m=1的时候怎么做。我们可以设计一个状态dp[i][j]表示选到i这个位置且选择了j段的最大和。转移有两种情况，一是这个i位置不选进去，则从dp[i-1][j]转移过来；二是选进去，则枚举这个第j段的起点k，从dp[k-1][j-1]转移过来，加上这个第j段的和。
m=2的时候实际可以把上下两行拼一起做，因此矩形要么只有一行宽要么就是两行宽。设计状态dp[i][j][p]表示第一行到i位置，第二行到j位置，且分了p段的状态。i位置不选进去的情况变为2种，第一行不选进去和第二行不选进去，实际上第一第二都不选的情况已经包含进去了，可以从dp[i-1][j][p]和dp[i][j-1][p]转移过来。选进去的话，矩形全在第一行/全在第二行/两行都有三种情况都要枚举，即可以从dp[i][k][p-1]、dp[k][j][p-1]和dp[k][k][p-1]转移而来。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register char c = fgc(); register LL res = 0, neg = 1;
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105;

int n, m, k, mat[MAXN][3], dp[MAXN][MAXN][15], sum[MAXN][3];

int main() {
    n = readint(); m = readint(); k = readint();
    for(int i = 1; i <= n; i++) {
        sum[i][0] = sum[i - 1][0];
        for(int j = 1; j <= m; j++) {
            mat[i][j] = readint();
            sum[i][j] = mat[i][j] + sum[i - 1][j];
            sum[i][0] += mat[i][j];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int p = 1; p <= k; p++) {
                dp[i][j][p] = std::max(dp[i][j - 1][p], dp[i - 1][j][p]);
                for(int q = 1; q <= i; q++) {
                    dp[i][j][p] = std::max(dp[i][j][p], 
                        dp[q - 1][j][p - 1] + sum[i][1] - sum[q - 1][1]);
                }
                for(int q = 1; q <= j; q++) {
                    dp[i][j][p] = std::max(dp[i][j][p], 
                        dp[i][q - 1][p - 1] + sum[j][2] - sum[q - 1][2]);
                }
                for(int q = 1; q <= std::min(i, j); q++) {
                    dp[i][j][p] = std::max(dp[i][j][p], 
                        dp[q - 1][q - 1][p - 1] + sum[std::min(i, j)][0] - sum[q - 1][0]);
                }
            }
        }
    }
    printf("%d", dp[n][n][k]);
    return 0;
}