题目

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

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

输出描述:
只有一行为k个子矩阵分值之和最大为多少。


解析

1)知识点

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

2)看题目

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

3)算法分析

  1. 这道题我们分析一下,其实也就是一道多种情况判断的dp罢了。
  2. 说到dp,那就是:动态规划最重要的就是递推和dp数组的含义
  3. 首先dp数组的含义就涉及到了我们这道题dp的中心思想:
    1. 我们一维的时候就是一个线性的dp+前缀和求区间值
    2. 然后这道题,我们一个m = 2的情况,也就是两条线罢了,单纯的组合起来就好了。
    3. 所以我们可以建立一个三维的dp:dp[第一列位置][第二列的位置][选取k个区块] = 最大区块和
  4. 然后就是递推了呢:
    1. 递推也就是这么几个点,首先两条线性的时候就可以单纯的线性判断。
    2. 如果两边判断的位置相等的时候呢,我们就可以判断一下同时取两边的情况了。
  5. 说了这么多,我还没讲到线性的怎么写:
    1. 我们就是简单的不好的就用区间代替就好了:
      for (int l = 0; l < i; l++)
              dp[i][k] = max(dp[i][k], dp[l][k - 1] + sum[i] - sum[l]);
      //i为数组位置,k为选取区间数量
  6. 就是如此。

4)算法操作

  1. 操作主要就是讲一下怎么递推了嘛。
  2. 其实就是枚举一下第一列,枚举一下第二列,再枚举一下选取空间而已。十分暴力的dp。
  3. 所以我们先做一个暴力三重循环:
    for (int i = 1; i <= n; i++)//枚举第一列
        for (int j = 1; j <= n; j++)//枚举第二列
            for (int k = 1; k <= num; k++)//枚举选取次数
    
  4. 然后最第一列第二列,还有一二列同时选的情况做个更新:
    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);
        }
    
  5. 最后输出最后一个位置的就好了:
    cout << dp[n][n][num] << endl;

5)打代码

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


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;
}
//函数区