激光炸弹
地图上有 N个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 N行，每行输入一组数据，每组数据包括三个整数 Xi, Yi, Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0 ≤ R ≤ 109
0 < N ≤ 10000
0 ≤ Xi,Y i ≤ 5000
0 ≤ W i≤ 1000
输入样例：
2 1 0 0 1 1 1 1
输出样例：
1
#include<iostream> using namespace std; int s[5010][5010]; int n, r, m; int main() { int cut; cin >> cut >> r; r = min(5001, r); //避免r*r的范围大于坐标系的范围引起错误 int i = 0, j = 0; n = m = r; //n和m 可能小于r引发边界问题 还有一种方式：直接将n和m取最大值5010，省去了后面确定坐 for (i = 0; i < cut; i++) //标系边界的麻烦，即第18行可以省略 { int x, y, w; cin >> x >> y >> w; x++, y++; //自加的作用是使得坐标从1开始 s[x][y] += w; n = max(n, x), m = max(m, y); //确定坐标系的边界 } for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //前缀和用一个数组处理 节省空间 } } int res = 0; for (i = r; i <= n; i++) //注意：i,j 要以 r 作为起始位置 { for (j = r; j <= m; j++) { int temp = s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]; res = max(res, temp); } } cout << res << endl; return 0; }
