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

[SCOI2005]最大子矩阵

https://ac.nowcoder.com/acm/problem/20242

题目

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

输入描述：

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

输出描述：

只有一行为k个子矩阵分值之和最大为多少。

解析

1）知识点

这是一道动态规划的题目。

2）看题目

首先看题目，就是让我们在矩阵里面找k个不重叠矩阵让他们加起来最大。
题目给的条件就很奇妙，m最大才2，n最大也才1e2，说明我们开个三维dp数组或者来个三重循环都不是问题。

3）算法分析

这道题我们分析一下，其实也就是一道多种情况判断的dp罢了。
说到dp，那就是：动态规划最重要的就是递推和dp数组的含义。
首先dp数组的含义就涉及到了我们这道题dp的中心思想：
1. 我们一维的时候就是一个线性的dp+前缀和求区间值。
2. 然后这道题，我们一个m = 2的情况，也就是两条线罢了，单纯的组合起来就好了。
3. 所以我们可以建立一个三维的dp：dp[第一列位置][第二列的位置][选取k个区块] = 最大区块和。
然后就是递推了呢：
1. 递推也就是这么几个点，首先两条线性的时候就可以单纯的线性判断。
2. 如果两边判断的位置相等的时候呢，我们就可以判断一下同时取两边的情况了。

说了这么多，我还没讲到线性的怎么写：

我们就是简单的不好的就用区间代替就好了：

for (int l = 0; l < i; l++)
        dp[i][k] = max(dp[i][k], dp[l][k - 1] + sum[i] - sum[l]);
//i为数组位置，k为选取区间数量

就是如此。

4）算法操作

操作主要就是讲一下怎么递推了嘛。
其实就是枚举一下第一列，枚举一下第二列，再枚举一下选取空间而已。十分暴力的dp。

所以我们先做一个暴力三重循环：

for (int i = 1; i <= n; i++)//枚举第一列
    for (int j = 1; j <= n; j++)//枚举第二列
        for (int k = 1; k <= num; k++)//枚举选取次数

然后最第一列第二列，还有一二列同时选的情况做个更新：

dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k]);
for (int l = 0; l < i; l++)
    dp[i][j][k] = max(dp[i][j][k], dp[l][j][k - 1] + sum[i][0] - sum[l][0]);
for (int l = 0; l < j; l++)
    dp[i][j][k] = max(dp[i][j][k], dp[i][l][k - 1] + sum[j][1] - sum[l][1]);
if (i == j)
    for (int l = 0; l < i; l++) {
            int sm0 = sum[i][0] - sum[l][0];
        int sm1 = sum[j][1] - sum[l][1];
        dp[i][j][k] = max(dp[i][j][k], dp[l][l][k - 1] + sm0 + sm1);
    }

最后输出最后一个位置的就好了：
```
cout << dp[n][n][num] << endl;
```

5）打代码

首先输入数据。
然后就阔以开始暴力dp啦。
下面全代码~

AC代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e2 + 7;
int n, m, num;
int sum[MAX][2], dp[MAX][MAX][17];
//全局变量区

int main() {
    IOS;
    cin >> n >> m >> num;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m; j++) {
            cin >> sum[i][j];
            sum[i][j] += sum[i - 1][j];
        }
    for (int i = 1; i <= n; i++)//枚举第一列
        for (int j = 1; j <= n; j++)//枚举第二列
            for (int k = 1; k <= num; k++) {//枚举选取次数
                dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k]);
                for (int l = 0; l < i; l++)
                    dp[i][j][k] = max(dp[i][j][k], dp[l][j][k - 1] + sum[i][0] - sum[l][0]);
                for (int l = 0; l < j; l++)
                    dp[i][j][k] = max(dp[i][j][k], dp[i][l][k - 1] + sum[j][1] - sum[l][1]);
                if (i == j)
                    for (int l = 0; l < i; l++) {
                        int sm0 = sum[i][0] - sum[l][0];
                        int sm1 = sum[j][1] - sum[l][1];
                        dp[i][j][k] = max(dp[i][j][k], dp[l][l][k - 1] + sm0 + sm1);
                    }
            }
    cout << dp[n][n][num] << endl;
    return 0;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏