题目:
地图上有 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
[
i
]
[
j
]
=
S
[
i
−
1
]
[
j
]
+
S
[
i
]
[
j
−
1
]
−
S
[
i
−
1
]
[
j
−
1
]
+
A
[
i
]
[
j
]
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]
S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+A[i][j]
对于任意一个边长 R 正方形:
S
=
S
[
i
]
[
j
]
−
S
[
i
−
R
]
[
j
]
−
S
[
i
]
[
j
−
R
]
+
S
[
i
−
R
]
[
j
−
R
]
S = S[i][j] - S[i-R][j] - S[i][j-R] + S[i-R][j-R]
S=S[i][j]−S[i−R][j]−S[i][j−R]+S[i−R][j−R]
算法:
import java.util.*;
public class Main {
public static int MAX = 5010;
public static int[][] s = new int[MAX][MAX];
public static int N, R;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
R = scanner.nextInt();
int x, y, w;
int xMax = 0, yMax = 0;
scanner.nextLine();
for(int i = 0; i < N; i++) {
String[] str = scanner.nextLine().split(" ");
x = Integer.parseInt(str[0]);
y = Integer.parseInt(str[1]);
w = Integer.parseInt(str[2]);
x++; y++;
s[x][y] += w;
xMax = Math.max(xMax, x);
yMax = Math.max(yMax, y);
}
int ans = 0;
for(int i = 1; i <= xMax ; i++) {
for(int j = 1; j <= yMax; j++) {
// 这里利用动态规划思路求S
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i-1][j-1];
// 这里利用S求正方形面积。边长不够 R 直接求到左上角的矩形。
x = i - R >= 0 ? i-R : 0;
y = j - R >= 0 ? j-R : 0;
int area = s[i][j] - s[x][j] -s[i][y] + s[x][y];
ans = Math.max(ans, area);
}
}
System.out.println(ans);
}
}