地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0≤R≤10^9
0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1
题目思路：
二维前缀和
此题如果开两个
s
u
m
[
5005
]
[
5005
]
sum[5005][5005]
sum[5005][5005]的数组，一个用来存输入数据，一个用来存前缀和空间就超了，所以压缩到一个里面
计算前缀和矩阵
S
(
x
,
y
)
=
S
(
x
−
1
,
y
)
+
S
(
x
,
y
−
1
)
−
S
(
x
−
1
,
y
−
1
)
+
a
[
x
]
[
y
]
S(x,y) = S(x-1,y)+S(x,y-1)-S(x-1,y-1)+a[x][y]
S(x,y)=S(x−1,y)+S(x,y−1)−S(x−1,y−1)+a[x][y];
利用前缀和矩阵，计算一个子矩阵的和
S
[
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
]
=
S
(
x
2
,
y
2
)
−
S
(
x
2
,
y
1
−
1
)
−
S
(
x
1
−
1
,
y
2
)
+
S
(
x
1
−
1
,
y
1
−
1
)
S[(x1,y1),(x2,y2)] = S(x2,y2)-S(x2,y1-1)-S(x1-1,y2)+S(x1-1,y1-1)
S[(x1,y1),(x2,y2)]=S(x2,y2)−S(x2,y1−1)−S(x1−1,y2)+S(x1−1,y1−1);
可以自行画图得出公式
这个是求子矩阵和
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5005;
int sum[5005][5005];
//二维前缀和
int main()
{
int n,r;
int s = 0;
scanf("%d%d", &n, &r);
for(int i=1; i<=n; ++i){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
sum[x+1][y+1] += v;
s = max(s,max(x,y));
}
s++;
for(int i=1; i<=s; ++i){
for(int j=1; j<=s; ++j){
// cout<<sum[i-1][j]<<' '<<sum[i][j-1]<<' '<<a[i-1][j-1]<<' '<<a[i][j]<<endl;
sum[i][j] += sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
// cout<<sum[i][j]<<' ';
}
// cout<<endl;
}
if(r>5001){
cout<<sum[s][s]<<endl;
return 0;
}
int res = 0;
for(int i=1; i<=s-r+1; ++i){
for(int j=1; j<=s-r+1; ++j){
int x1 = i,y1 = j,x2 = i+r-1,y2 = j+r-1;
int t = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
res = max(res,t);
}
}
cout<<res<<endl;
return 0;
}