P1719. 最大加权矩形

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 208 阅读时长 ≈ 1 分钟

考点

  • 前缀和
  • 最大子段和

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e2 + 50;
int n, pre[maxn][maxn];

void init() {
  // 初始化二维前缀和数组
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> pre[i][j];
      pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
    }
  }
}

int query(int x1, int y1, int x2, int y2) {
  return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}

int main() {
  cin >> n;
  init();
  int ans = 0xc0c0c0c0;
  // 枚举矩形的上下边界
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      int dp = 0xc0c0c0c0;
      // 控制上下边界后，按“最大子段和”的思路求子矩阵和
      for (int k = 1; k <= n; ++k) {
        int cur = query(i, k, j, k);
        dp = max(dp + cur, cur);
        ans = max(ans, dp);
      }
    }
  }
  cout << ans;
  return 0;
}

思路

二维前缀和的模板题+最大子段和