题意

给定一个 的矩阵，。求从矩阵中选出 个不相交小矩形，使得它们的权值和最大。

题解

先研究 的情况。显然这等价于经典的“最大 子段和”问题。可以在线性时间 内解决。

再研究 的情况。设 为前 行中选出了 个矩形可以得到的最大权值和。那么转移方程为
三个选项中取最大值。其中 表示第 列中，第 行到第 行之间的一段数的最大 子段和的值。这个可以在 时间内预处理得到。

初始条件为 时 。答案为 。

总的时间复杂度为 。应当可以优化到更低。

#include <bits/stdc++.h>
using namespace std;
int sumg[105] = {0}, sumh[105] = {0};
int n, m, k, a[105][2];
int g[105][105][12], h[105][105][12];
int f[105][12];
void solve1(){
    cout << g[1][n][k] << endl;
}
void solve2(){
    for (int i = 1; i <= n; ++i)
        sumh[i] = sumh[i - 1] + a[i][1];
    for (int i = 1; i <= n; ++i){
        for (int j = i - 1; j <= n; ++j)
            h[i][j][0] = 0;
        for (int t = 1; t <= k; ++t){
            int maxi = h[i][i - 1][t - 1] - sumh[i - 1];
            for (int j = i; j <= n; ++j){
                h[i][j][t] = max(h[i][j][t], sumh[j] + maxi);
                maxi = max(maxi, h[i][j][t - 1] - sumh[j]);
                h[i][j][t] = max(h[i][j][t], h[i][j - 1][t]);
            }
        }
    }
    for (int t = 1; t <= k; ++t){
        int maxi = f[0][t - 1];
        for (int i = 1; i <= n; ++i){
            f[i][t] = max(f[i][t], sumg[i] + sumh[i] + maxi);
            maxi = max(maxi, f[i][t - 1] - sumg[i] - sumh[i]);
            for (int j = i - 1; j >= 0; --j){
                for (int p = 1; p <= t; ++p)
                    for (int u = 0; u <= p; ++u)
                        f[i][t] = max(f[i][t], f[j][t - p] + g[j + 1][i][u] + h[j + 1][i][p - u]);       
            }
            f[i][t] = max(f[i][t], f[i - 1][t]);
        }
    }
    cout << f[n][k] << endl;
}
int main(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    }
    memset(f, 0xDF, sizeof(f));
    memset(g, 0xDF, sizeof(g));
    memset(h, 0xDF, sizeof(h));
    for (int i = 0; i <= n; ++i)
        f[i][0] = 0;
    for (int i = 1; i <= n; ++i)
        sumg[i] = sumg[i - 1] + a[i][0];
    for (int i = 1; i <= n; ++i){
        for (int j = i - 1; j <= n; ++j)
            g[i][j][0] = 0;
        for (int t = 1; t <= k; ++t){
            int maxi = g[i][i - 1][t - 1] - sumg[i - 1];
            for (int j = i; j <= n; ++j){
                g[i][j][t] = max(g[i][j][t], sumg[j] + maxi);
                maxi = max(maxi, g[i][j][t - 1] - sumg[j]);
                g[i][j][t] = max(g[i][j][t], g[i][j - 1][t]);
            }
        }
    }
    if (m == 1) solve1();
    else solve2();
    return 0;
}