【每日一题】【6月8日】[SCOI2005]最大子矩阵

题意：

给定一个 的矩阵，从中选出 个互不重叠的子矩阵，使得总分值最大。

其中 。

题解：

注意到 。

先考虑 的情况，是一个比较经典的最大 子段和问题，可以用 求解，复杂度为 。具体做法这里就不说了。

再考虑 的情况，由 的求解做法接着往下考虑。子矩阵可以是第一列的连续行，或者第二列的连续行，或者两列的连续行。

因此可以设计 状态：

表示第一列 行，第二列 行，其中选取了 个子矩阵的最大和。

注意这里并不包含第一列以 为结尾，第二列以 为结尾，即 必选。

那么不选取以 或 不选 的转移为：

选择一个以 为结尾的子矩阵的转移为：

选择一个以 结尾的子矩阵的转移为：

选择一个包含两列的子矩阵，需满足 的条件，此时转移为：

这样对 的情况就完成了。复杂度为 。

对于 的情况，我们可以令所有的 ，这样就可以保证转移时选取第一列是最优的，从而合并两种情况。

注意需要考虑元素全为负数的情况，写到一半才发现这部分还是没处理好，测试数据刚好比较弱。

可以测一下以下两组数据：

3 2 2
-1 -1
-1 -1
-1 -1

3 1 2
-1
-1
-1

Code：

#include <bits/stdc++.h>
using namespace std;
const int inf = -32768;
int dp[11][101][101], n, m, k, sum[2][101];

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) 
        for(int j = 0; j < 2; j++) {
            int x = inf; 
            if(j < m) cin >> x;
            sum[j][i] = sum[j][i - 1] + x;
        }

    for(int i = 1; i <= k; i++)
        for(int x = 0; x <= n; x++)
            for(int y = 0; y <= n; y++) {
                dp[i][x][y] = -0x3f3f3f3f;
                if(x) dp[i][x][y] = max(dp[i][x][y], dp[i][x - 1][y]);
                if(y) dp[i][x][y] = max(dp[i][x][y], dp[i][x][y - 1]);
                if(x && y) dp[i][x][y] = max(dp[i][x][y], dp[i][x - 1][y - 1]);
                if(i) {
                    for(int t = 0; t < x; t++) dp[i][x][y] = max(dp[i][x][y], dp[i - 1][t][y] + sum[0][x] - sum[0][t]);
                    for(int t = 0; t < y; t++) dp[i][x][y] = max(dp[i][x][y], dp[i - 1][x][t] + sum[1][y] - sum[1][t]);
                    if(x == y)
                    for(int t = 0; t < x; t++) dp[i][x][y] = max(dp[i][x][y], dp[i - 1][t][t] + sum[0][x] - sum[0][t] + sum[1][y] - sum[1][t]);
                }
            }
    cout << dp[k][n][n] << endl;
    return 0;
}