2526 激光炸弹
大约 4 分钟
2526 激光炸弹
【算法】 二维前缀和
【C++】 二维数组、二维前缀和、坐标处理
【难度】 普及/提高−
一、题目简述
地图上有 个目标点(),坐标 (),每个有价值 。激光炸弹覆盖 的正方形(边与坐标轴平行),求能炸掉的最大总价值。
二、解题思路
数据规模分析
坐标范围 0~5000,地图网格是 。 可能非常大(题目中可达 ),但实际上 超过 就和覆盖全地图一样,取 即可。
,,建前缀和需要遍历所有网格点,约 次运算,在 1 秒内可以完成。
算法步骤
- 坐标转换:原坐标从 0 开始,前缀和习惯从 1 开始,所以将所有坐标
- 注意同位置多目标:多个目标可能出现在同一坐标,价值要累加(
+=而非=) - 构建二维前缀和
- 枚举正方形:以每个 为右下角(),计算 正方形内的总价值
- 取最大值
正方形查询公式
以 为右下角的 正方形,其左上角为 。因此查询范围是 。
用二维前缀和公式(注意边界是 而非 ):
图解
j-R j
+-----+-----------------+
| | |
i-R|-----+-----------------+
| | R x R 正方形 |
| | |
i|-----+-----------------+
| | |
+-----+-----------------+包含 行 列,所以从 到 。在二维前缀和公式中,去掉的部分是前 行(即 )和前 列(即 )。
手动模拟
假设 ,地图 :
1 2 3
4 5 6
7 8 9前缀和构建后(略)。以 为右下角的 正方形覆盖 ,即左上角 :
即四数之和 。
以 为右下角的 正方形:
覆盖的是 ,即 。
坐标转换说明
题目给的坐标范围是 ~ , 后变为 ~ 。所以实际有效坐标从 到 ,数组开到 N = 5005 确保不越界。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int pre[N][N];
int main() {
int n, R;
scanf("%d%d", &n, &R);
R = min(R, 5001); // R 太大没有意义
for (int i = 0; i < n; i++) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
pre[x + 1][y + 1] += w; // 坐标+1,多重目标累加
}
// 二维前缀和
for (int i = 1; i <= 5001; i++) {
for (int j = 1; j <= 5001; j++) {
pre[i][j] += pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
}
}
int ans = 0;
for (int i = R; i <= 5001; i++) {
for (int j = R; j <= 5001; j++) {
int sum = pre[i][j] - pre[i-R][j] - pre[i][j-R] + pre[i-R][j-R];
ans = max(ans, sum);
}
}
printf("%d\n", ans);
return 0;
}四、复杂度分析
- 时间复杂度:。这是固定的,不随 和 变化。在 秒时限内通常可以通过。
- 空间复杂度: MB( 个
int约 MB)。如果内存限制较紧(如 128 MB),需要注意:- 在
pre数组上原地构建前缀和(不另开数组),如代码所示 - 如果仍超内存,可将
int改为short(价值范围不允许则不可),或改用vector<vector<int>>(但可能更慢)
- 在
五、易错点
- 坐标从 0 开始:必须 转换为从 1 开始,否则
i-R会出现负下标。 - 可能大于 5001:需要
R = min(R, 5001),否则数组越界。 - 同一位置多个目标:用
+=而非=存价值。 - 正方形边界计算:正方形包含 个位置,查询时减去的边界是 (不是 也不是 )。可以这样理解: 时查询 ,公式变为 ,恰好是单点的前缀和还原。
- 枚举范围:右下角从 开始枚举,因为 正方形必须完全在地图内。
六、扩展知识
固定窗口 + 前缀和
本模板(固定窗口 + 前缀和)是一个常见模式:先建前缀和,再用一个固定大小的窗口滑动,每次 查询窗口内总和。类似技巧可应用于:
- 任意 矩形的最大和
- 滑动窗口的平均值计算
- 图像处理中的均值滤波
内存优化技巧
如果内存吃紧,可以将 pre[k][*] 和 pre[k-1][*] 这两行交替复用,将空间压到 :
int pre[2][N]; // 滚动数组
// 但实现较复杂,一般情况下不建议类似题目
- 子矩阵求和:二维前缀和基础
- 差分矩阵:二维差分
- 最大加权矩形:降维 + 一维最大子段和
