C++五级GESP认证：二维前缀和算法实战，解决洛谷P2004领地选择问题

C++五级GESP认证：二维前缀和算法实战，解决洛谷P2004领地选择问题

题目要求

题目描述

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 C×C 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数 N, M, C，表示地图的宽和长以及首都的边长。

接下来 N 行每行 M 个整数，表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数，表示首都左上角的坐标。保证最优解是唯一的。

输入输出样例 #1

输入 #1

3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

输出 #1

1 2

说明/提示

对于 60% 的数据， N, M ≤ 50。

对于 90% 的数据， N, M ≤ 300。

对于 100% 的数据， 1≤N, M≤1000， 1≤C≤min(N, M)。每块地价值的绝对值不超过 32767。

题目分析

本题要求在 N×M 的矩阵中找到一个 C×C 的正方形区域，使得该区域内所有元素的和最大。

1. 暴力解法

如果枚举每一个可能的左上角坐标(i, j)，然后通过两层循环计算以(i, j)为起点的C×C区域的和，单次计算的复杂度是O(C²)。总的时间复杂度将达到O(N M C²)。

考虑到题目中N, M最大为1000，如果C也接近1000，计算量将达到O(10^9)级别，显然会超时。

2. 优化的解法：二维前缀和

为了在常数时间内计算任意一个子矩阵的和，我们需要使用二维前缀和这一重要的算法优化技巧。通过系统性地学习和应用这类算法，可以有效提升解决复杂数据结构问题的能力。

定义 pre[i][j] 表示以 (1,1) 为左上角，(i,j) 为右下角的矩形区域内所有元素的和。

预处理公式：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]
其中 a[i][j] 是当前位置的数值。通过上述递推，我们可以在 O(N*M) 的时间内计算出所有前缀和。

子矩阵求和公式：
对于任意一个以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵，其元素和可以用于求解大规模网络数据流或复杂系统状态统计等场景，其公式为：
sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]
可以在 O(1) 时间内完成计算。

在本题中，我们要找的是边长为C的正方形。如果左上角是(i, j)，那么右下角就是(i+C-1, j+C-1)。

3. 算法代码流程

1. 读取 N, M, C 以及矩阵数据。
2. 利用递推公式计算二维前缀和数组 pre。
3. 枚举所有可能的首都左上角坐标 (i, j)，其中 i+C-1 <= N 且 j+C-1 <= M。
4. 利用 O(1) 的公式计算当前正方形区域的价值和，并维护最大值及其对应的坐标。
5. 输出结果。

4. 注意事项

• 数据范围：虽然单个格子的价值在 int 范围内，但 C² 个格子累加可能会超过 int 的表示范围，因此前缀和数组和结果变量需要使用 long long 类型。
• 初始值：由于地块价值可能为负数，最大价值 max_sum 初始化时应设为一个极小值（如 LLONG_MIN），而不能设为 0。

示例代码

#include <climits>
#include <iostream>
typedef long long ll;

// a[i][j] 存储每个格子的价值
// pre[i][j] 存储 (1,1) 到 (i,j) 的矩形区域内的价值总和（二维前缀和）
int a[1005][1005];
ll pre[1005][1005];

int main() {
    // N, M 为地图的宽和长，C 为首都的边长
    int N, M, C;
    std::cin >> N >> M >> C;

    // 读取输入并计算二维前缀和
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            std::cin >> a[i][j];
            // 二维前缀和公式：
            // 当前点的前缀和 = 上方的前缀和 + 左方的前缀和 -
            // 左上方重复计算的部分 + 当前点的值
            pre[i][j] =
                pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
        }
    }

    // 初始化最大价值为 long long 的最小值，防止因负数导致错误
    ll max_sum = LLONG_MIN;
    int x, y; // 记录最优解的左上角坐标

    // 枚举所有可能的首都左上角坐标 (i, j)
    // 注意边界条件：i + C - 1 <= N 且 j + C - 1 <= M
    for (int i = 1; i + C - 1 <= N; i++) {
        for (int j = 1; j + C - 1 <= M; j++) {
            // 利用二维前缀和计算以 (i, j) 为左上角，边长为 C
            // 的正方形区域的价值和 公式：右下角前缀和 - 上方多余部分 -
            // 左方多余部分 + 左上方多减的部分
            ll cur_sum = pre[i + C - 1][j + C - 1] - pre[i - 1][j + C - 1] -
                         pre[i + C - 1][j - 1] + pre[i - 1][j - 1];

            // 如果当前区域价值更大，则更新最大值和坐标
            if (cur_sum > max_sum) {
                max_sum = cur_sum;
                x = i;
                y = j;
            }
        }
    }

    // 输出结果
    std::cout << x << " " << y << "\n";
    return 0;
}

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