99. 激光炸弹
地图上有 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; }