激光炸弹
地图上有 \(N\) 个目标，用整数 \(Xi,Yi\)表示目标在地图上的位置，每个目标都有一个价值 \(Wi\)。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 \(R×R\) 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 \(N 和 R\)，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数 \(Xi,Yi,Wi，\)分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
\(0≤R≤109\)
\(0<N≤10000,\)
\(0≤Xi,Yi≤5000\)
\(0≤Wi≤1000\)
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1
注意
1.不能开两个数组，因为每个数组是\(5000*5000\)这么大，就是\(5000*5000*4bytes\)，\(5000*5000*4/1024/1024=95MB\)，这题的空间是168MB，所以两个数组会MLE
2.开一个数组，在自己身上求子矩阵的和
Code
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define endl '\n'
using namespace std;
const int N = 5010;
int s[N][N];
int n,r;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> r;
int mx = 0, my = 0;
while(n --){
int x,y,w;
cin >> x >> y >> w;
mx = max(mx,x+1);
my = max(my,y+1);
s[x + 1][y + 1] += w; //往右下移一格，方便求和,后面要记得
//坐标可能重复所以要+=
}
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]; //在原数组求前缀和
}
}
if(r >= max(mx,my)){ //r的数据范围可能大于整个地图，此时只需要求整个矩阵的和即可
cout << s[mx][my];
return 0;
}
int x2 = r,y2 = r,x1 = 1,y1 = 1;
int maxn = 0;
for(int dx = 0; dx + x2 <= 5001; dx ++){ //偏移量
for(int dy = 0; dy + y2 <= 5001; dy ++){
int x2t = dx + x2,y2t = dy + y2;
int x1t = dx + x1,y1t = dy + y1;
int ksum = s[x2t][y2t] - s[x1t - 1][y2t] - s[x2t][y1t - 1] + s[x1t - 1][y1t - 1];
maxn = max(maxn,ksum);
}
}
cout << maxn;
return 0;
}
