「SCOI 2005」最大子矩阵

题目大意：

因为最多只有两列，分类讨论即可。

#include <cstdio>

int dp[105][15], f[105][105][15], s1[105], s2[105], n, m, K;

int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    if (m == 1) {
        for (int i = 1, x; i <= n; ++i) {
            scanf("%d", &x);
            s1[i] = s1[i-1] + x;
        }
        for (int i = 1; i <= n; ++i) //到第i个位置
            for (int k = 1; k <= 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] + s1[i] - s1[j]);
            }
        printf("%d\n", dp[n][K]);
    } else {
        for (int i = 1, x, y; i <= n; ++i) {
            scanf("%d%d", &x, &y);
            s1[i] = s1[i-1] + x, s2[i] = s2[i-1] + y;
        }
        for (int k = 1; k <= K; ++k) //选了k个矩形
            for (int i = 1; i <= n; ++i) //第一列到i
                for (int j = 1; j <= n; ++j) { //第二列到j
                    f[i][j][k] = max(f[i-1][j][k], f[i][j-1][k]);
                    for (int l = 0; l < i; ++l) //第一列上一个矩形截止的位置
                        f[i][j][k] = max(f[i][j][k], f[l][j][k-1] + s1[i] - s1[l]);
                    for (int l = 0; l < j; ++l) //第二列上一个矩形截止的位置
                        f[i][j][k] = max(f[i][j][k], f[i][l][k-1] + s2[j] - s2[l]);
                    if (i == j) for (int l = 0; l < i; ++l)
                        f[i][j][k] = max(f[i][j][k], f[l][l][k-1] + s1[i] - s1[l] + s2[j] - s2[l]);
                }
        printf("%d\n", f[n][n][K]);
    }
    return 0;
}