争取每天早起一小时写一题emmm

Description

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

Solution

注意到
其实就是两列数字求最大连续子段和的变形
我们可以枚举当前第一列所处位置 i, 第二列所处位置 j, 当前已经取了 k 个矩阵
做 的状态转移
我们可以枚举上一个矩阵的终点位置，然后利用预处理前缀和的思想对每个方案取max

  • 第 k 个取第二列的情况
  • 第 k 个取第一列的情况
  • i == j, 第 k 个取一个t * 2 的小矩阵

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 100000000;
const int N = 5e5 + 5;
typedef long long ll;
const double pi = acos(-1.0);
const double EPS=1e-8;

int a[105][3], sum[105][3];
int dp[105][105][105];
int main() {
  int n, m, p;
  cin >> n >> m >> p;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> a[i][j];
      sum[i][j] = sum[i - 1][j] + a[i][j];
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      for(int k = 1; k <= p; k++) {
        dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]);
        for(int l = 0; l < j; l++) {
          dp[i][j][k] = max(dp[i][l][k - 1] + sum[j][2] - sum[l][2], dp[i][j][k]);
        }
        for(int l = 0; l < i; l++) {
          dp[i][j][k] = max(dp[l][j][k - 1] + sum[i][1] - sum[l][1], dp[i][j][k]);
        }
        if(i == j) {
          for(int l = 0; l < i; l++)
            dp[i][j][k] = max(dp[l][l][k - 1] + (sum[i][1] - sum[l][1]) + (sum[j][2] - sum[l][2]), dp[i][j][k]);
        }
      }
    }
  }
  cout << dp[n][n][p] << "\n";
  return 0;
}