题目
题目描述:这里有一个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; } //函数区