【题目来源】
洛谷：[P2280 HNOI2003] 激光炸弹 - 洛谷
【题目描述】
一种新型的激光炸弹，可以摧毁一个边长为 m 的正方形内的所有目标。现在地图上有 \(n\) 个目标，用整数 \(x_i\) , \(y_i\) 表示目标在地图上的位置，每个目标都有一个价值 \(v_i\)。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 \(m\) 的边必须与 \(x\) 轴，\(y\) 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。
现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。
可能存在多个目标在同一位置上的情况。
【输入】
输入的第一行为整数 \(n\) 和整数 \(m\)；
接下来的 \(n\) 行，每行有 \(3\) 个整数 \(x, y, v\)，表示一个目标的坐标与价值。
【输出】
输出仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过 \(32767\) ）。
【输入样例】
2 1
0 0 1
1 1 1
【输出样例】
1
【算法标签】
《洛谷 P2280 激光炸弹》 #动态规划,dp# #枚举# #前缀和# #各省省选# #湖南# #2003#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 5005; // 定义二维数组最大尺寸
int n, m; // n: 点数, m: 正方形边长
int a[N][N]; // 原始值数组
int s[N][N]; // 二维前缀和数组int main()
{// 输入点数和正方形边长cin >> n >> m;// 输入每个点的坐标和值for (int i = 1; i <= n; i++){int x, y, v;cin >> x >> y >> v;x++; y++; // 坐标偏移（从1开始）a[x][y] += v; // 累加值到对应位置}// 计算二维前缀和数组for (int i = 1; i <= 5001; i++){for (int j = 1; j <= 5001; j++){// 二维前缀和公式s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];}}int res = 0; // 存储最大和// 遍历所有可能的m×m正方形for (int i = m; i <= 5001; i++){for (int j = m; j <= 5001; j++){// 计算当前m×m正方形的和int current = s[i][j] - s[i-m][j] - s[i][j-m] + s[i-m][j-m];res = max(res, current); // 更新最大值}}// 输出最大和cout << res << endl;return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 10005; // 定义二维数组最大尺寸
int n, m; // n: 点数, m: 正方形边长
int a[N][N]; // 原始值数组
int s[N][N]; // 二维前缀和数组int main()
{// 输入点数和正方形边长cin >> n >> m;// 输入每个点的坐标和值for (int i = 1; i <= n; i++){int x, y, v;cin >> x >> y >> v;x++; y++; // 坐标偏移（从1开始）a[x][y] += v; // 累加值到对应位置}// 计算二维前缀和数组for (int i = 1; i <= 5005; i++){for (int j = 1; j <= 5005; j++){// 二维前缀和公式s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];}}int res = 0; // 存储最大和// 遍历所有可能的m×m正方形for (int i = m; i <= 5005; i++){for (int j = m; j <= 5005; j++){// 计算当前m×m正方形的和int current = s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m];res = max(res, current); // 更新最大值}}// 输出最大和cout << res << endl;return 0;
}
【运行结果】
2 1
0 0 1
1 1 1
1