文章

【GESP】C++五级/六级练习题（前缀和/动态规划考点） luogu-P1719 最大加权矩形

发表于
作者 OneCoder
次浏览 12 分钟阅读

GESP C++ 五级/六级练习题，二维前缀和的应用与优化。题目难度⭐⭐⭐☆☆，适合进阶练习二维数组处理和子矩阵求和，洛谷难度等级普及+/提高。

luogu-P1719 最大加权矩形

题目要求

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 $n\times n$ 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 $[-127,127]$ ,例如

0 –2 –7  0 
9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角：

9  2
-4  1
-1  8

和为 $15$。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：$n$，接下来是 $n$ 行 $n$ 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

输入输出样例 #1

输入 #1
1
2
3
4
5

4
0 -2 -7 0
 9 2 -6 2
-4 1 -4  1 
-1 8  0 -2
输出 #1
1

15

说明/提示

$1 \leq n\le 120$

题目分析

本题要求在一个 $N \times N$ 的矩阵中找到一个子矩阵，使得该子矩阵中所有元素的和最大。这是一个经典的“最大子矩阵和”问题。

数据范围与复杂度考虑： 题目给出 $N \le 120$。

  • 如果使用朴素的暴力法枚举所有子矩阵并求和，时间复杂度为 $O(N^6)$（枚举左上、右下坐标 $O(N^4)$，求和 $O(N^2)$），肯定超时。
  • 利用二维前缀和优化求和过程，可以将复杂度降至 $O(N^4)$。$120^4 \approx 2.07 \times 10^8$，在 1秒的时限下属于卡常数的边缘，C++ 开启优化（O2）一般能过，但不是最优解。
  • 结合 动态规划（最大子段和） 的思想，可以将复杂度降至 $O(N^3)$。$120^3 \approx 1.72 \times 10^6$，这完全可以通过，是本题的标准解法。

方法一：二维前缀和（暴力优化）

  1. 预处理：构建一个二维前缀和数组 pre_a[i][j]，表示以 $(1,1)$ 为左上角，$(i,j)$ 为右下角的矩形区域和。 递推公式：pre_a[i][j] = a[i][j] + pre_a[i-1][j] + pre_a[i][j-1] - pre_a[i-1][j-1]。
  2. 枚举：使用四层循环枚举子矩阵的左上角 $(i, j)$ 和右下角 $(k, l)$。
  3. 计算：利用容斥原理在 $O(1)$ 时间内计算出子矩阵的和： Sum = pre_a[k][l] - pre_a[i-1][l] - pre_a[k][j-1] + pre_a[i-1][j-1]。
  4. 更新：维护一个 max_sum 记录遇到的最大值。

方法二：降维 + Kadane算法（最优解）

这个方法的思路是将二维问题转化为一维问题，利用最大子段和的模型来求解。

  1. 确定上下边界：我们先枚举子矩阵的起始行 i 和 结束行 j（$1 \le i \le j \le N$）。这样就确定了子矩阵的高度范围。
  2. 列压缩：在行范围 $[i, j]$ 固定后，我们可以把每一列看作一个整体。计算每一列在这个行范围内的元素之和。
    • 设 col_sum[k] 为第 $k$ 列从第 $i$ 行到第 $j$ 行的元素和。col_sum[k] = a[i][k] + ... + a[j][k]。
    • 在代码实现中，可以在枚举 j 的过程中动态累加，不需要重复计算。即当 j 增加 1 时，只需将新的一行加到 col_sum 上。*
  3. 转化为一维最大子段和：现在问题变成了：在一个一维数组 col_sum 中，找到一个连续子段，使其和最大。这正是经典的 最大子段和问题，可以使用 Kadane算法（一种简单的动态规划/贪心思想）在 $O(N)$ 时间内解决。
    • 用一个变量 cur_sum：如果 cur_sum > 0，则 cur_sum += col_sum[k]（前面的和是正的，加上有益）；否则 cur_sum = col_sum[k]（前面的和是负的，拖后腿，不如另起炉灶）。

总结：

  • 方法一： 适合初学者理解二维前缀和，代码逻辑简单直接，对应 GESP 五级知识点。
  • 方法二： 融合了降维技巧和线性 DP，效率更高，对应 GESP 六级或更高阶的算法思维。

示例代码

方法一、前缀和（五级）

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
39
40
41
42
43
44
45

#include <climits>
#include <iostream>

// 定义最大矩阵大小，题目中 N <= 120
int a[125][125];
// pre_a[i][j] 表示从 (1,1) 到 (i,j) 的子矩阵元素之和（二维前缀和）
int pre_a[125][125];

int main() {
    int n;
    std::cin >> n;
    // 读取矩阵并计算二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cin >> a[i][j];
            // 二维前缀和公式：当前元素 + 上方区域 + 左方区域 - 左上重叠区域
            pre_a[i][j] = a[i][j] + pre_a[i - 1][j] + pre_a[i][j - 1] -
                          pre_a[i - 1][j - 1];
        }
    }

    // 初始化最大和为最小整数
    int max_sum = INT_MIN;

    // 暴力枚举所有可能的子矩阵
    // (i, j) 为子矩阵的左上角坐标
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // (k, l) 为子矩阵的右下角坐标
            for (int k = i; k <= n; k++) {
                // 注意：这里原代码是 l < n，会导致漏掉最后一列，已修正为 l <= n
                for (int l = j; l <= n; l++) {
                    // 利用容斥原理计算子矩阵 (i,j) 到 (k,l) 的和
                    // Sum = pre_a[k][l] - 上方多余 - 左方多余 +
                    // 左上重复减去的部分
                    int cur_sum = pre_a[k][l] - pre_a[i - 1][l] -
                                  pre_a[k][j - 1] + pre_a[i - 1][j - 1];
                    max_sum = std::max(max_sum, cur_sum);
                }
            }
        }
    }
    std::cout << max_sum << std::endl;
    return 0;
}

方法二、Kadane算法

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <algorithm>
#include <climits>
#include <iostream>

// 定义最大矩阵大小，题目中 N <= 120
int a[125][125];
// col_sum[k] 用于存储压缩后的第 k 列的和
int col_sum[125];

int main() {
    int n;
    std::cin >> n;
    // 读取 N*N 矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cin >> a[i][j];
        }
    }

    // 初始化最大和为最小整数，防止全负数情况
    int max_sum = INT_MIN;

    // 枚举矩形的上边界 i
    for (int i = 1; i <= n; i++) {
        // 每次更换上边界时，清空 col_sum 数组
        // 注意：这里需要清空 1 到 n 的范围，所以 fill 的结束迭代器是 col_sum +
        // n + 1
        std::fill(col_sum, col_sum + n + 1, 0);

        // 枚举矩形的下边界 j，从 i 开始向下延伸
        for (int j = i; j <= n; j++) {
            // 将第 j 行的数值累加到 col_sum 中
            // 此时 col_sum[k] 表示第 k 列从第 i 行到第 j 行的元素之和
            // 这一步实现了将二维子矩阵压缩为一维数组
            for (int k = 1; k <= n; k++) {
                col_sum[k] += a[j][k];
            }

            // 对一维数组 col_sum 进行最大子段和计算 (Kadane 算法)
            // cur_sum 记录当前连续子段的和
            int cur_sum = 0;
            for (int k = 1; k <= n; k++) {
                // 如果当前和大于 0，则继续累加，因为对后续有增益
                if (cur_sum > 0) {
                    cur_sum += col_sum[k];
                } else {
                    // 如果当前和小于等于
                    // 0，则丢弃之前的子段，从当前元素重新开始
                    cur_sum = col_sum[k];
                }
                // 更新全局最大和
                max_sum = std::max(max_sum, cur_sum);
            }
        }
    }
    std::cout << max_sum << std::endl;
    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
GESP, 五级
GESP C++ 前缀和 动态规划
本文由作者按照 CC BY-NC-SA 4.0 进行授权