题目描述
一种新型的激光炸弹,可以摧毁一个边长为 R 的正方形内的所有的目标。
现在地图上有 N 个目标,用整数Xi,Yi表示目标在地图上的位置,每个目标都有一个价值Wi。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个边长为 R 的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标不会被摧毁。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来N行,每行输入一组数据,每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标,y坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0<N≤10000,
0≤Xi,Yi≤5000
样例
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
我的思路
整体思路:用一个边长为r的正方形去遍历整个矩阵,极限时间复杂度是: 0(n * n);每次都算出该正方形中覆盖的c的总和,思路和二维前缀和一样。
实现细节:把整个坐标系中的点看成是边长为1的正方形的中心;这样给出的半径r就是正方形的边长;首先初始化a[][]数组,若是输入 x, y, c,则, 先x自加1, y加1, 然后,a[x][y] = c; 这样写并不会影响最终的答案,起到的作用是方便了前缀和数组sum的初始化;然后在初始化a数组之后,进行前缀和数组sum的初始化的时候可以直接使用数组a[][], 其目的是节约空间复杂度,sum初始化方程:a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j],因为是从左到右,从上到下进行sum的初始化所以直接用a数组是没有问题的。最后还有一个问题,我们循环的边界是多少,设行边界为xx, 列边界为yy,那么最开始xx = yy = r, 当我们在输入x, y, c的时候可以不断的更新 xx, yy.
AC代码如下:
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
#define inf 0x3fffffff
const int maxn = 5e3 + 5;
int a[maxn][maxn];
int main(void) {
int n, r;
scanf("%d%d", &n, &r);
int x, y, c, xx, yy;
xx = yy = r;
for(int i = 1; i <= n; i++) {
scanf("%d%d%d", &x, &y, &c);
a[++x][++y] += c;
xx = max(xx, x);
yy = max(yy, y);
}
for(int i = 1; i <= xx; i++)
for(int j = 1; j <= yy; j++)
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
int ans = -inf;
for(int i = r; i <= xx; i++)
for(int j = r; j <= yy; j++)
ans = max(ans, a[i][j] - a[i - r][j] - a[i][j - r] + a[i - r][j - r]);
printf("%d\n",ans);
return 0;
}