【每日一题】[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的中心思想：
- 我们一维的时候就是一个线性的dp+前缀和求区间值。
- 然后这道题，我们一个m = 2的情况，也就是两条线罢了，单纯的组合起来就好了。
- 所以我们可以建立一个三维的dp：dp[第一列位置][第二列的位置][选取k个区块] = 最大区块和。
- 然后就是递推了呢：
- 递推也就是这么几个点，首先两条线性的时候就可以单纯的线性判断。
- 如果两边判断的位置相等的时候呢，我们就可以判断一下同时取两边的情况了。
- 说了这么多，我还没讲到线性的怎么写：
- 我们就是简单的不好的就用区间代替就好了：
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;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
查看10道真题和解析
投递牛客等公司10个岗位 >