99. 激光炸弹
摘要
Title: 99. 激光炸弹
Tag: 二位前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
99. 激光炸弹
-
题意
地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。 -
思路
R×R个位置的正方形，如果包含边界，是可以炸到(R+1)×(R+1)个点的，但题目说不包含边界，所以只能最多炸R×R个点
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34'''
Author: NEFU AB-IN
Date: 2022-02-22 22:58:59
FilePath: \ACM\Acwing\99.py
LastEditTime: 2022-02-23 09:55:02
'''
N = int(5e3 + 10)
a = [[0] * N for _ in range(N)]
s = [[0] * N for _ in range(N)]
n, r = map(int, input().split())
r = min(r, 5001)
xx, yy = r, r #为了防止边界问题，首先将x和y的最大值变成r，这样一定能确保后面可以遍历
for i in range(n):
x, y, w = map(int, input().split())
a[x + 1][y + 1] += w
xx = max(xx, x + 1)
yy = max(yy, y + 1)
for i in range(1, xx + 1):
for j in range(1, yy + 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
res = 0
for i in range(r, xx + 1):
for j in range(r, yy + 1):
x1, y1, x2, y2 = i - r + 1, j - r + 1, i, j
res = max(
res, s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1])
print(res)