题目描述
地图上有 N 个目标,用整数 Xi,Yi 表示目标在地图上的位置,每个目标都有一个价值 Wi。
注意:不同目标可能在同一位置。
现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 x,y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来 N 行,每行输入一组数据,每组数据包括三个整数 Xi,Yi,Wi,分别代表目标的 x 坐标,y 坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0≤R≤109
0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000
样例
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
算法1
(二维前缀和/二维任意边长矩阵和)
看大佬的
C 代码
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
int main(){
int n,r,i,j,t;
scanf("%d %d",&n,&r);
int sum[5002][5002]; //二维前缀和 sum[i][j]为[0,0]~[i,j]的矩阵的和 并把第一行 第一列作为边界 额外加上 这样后面可以省去额外的判断
memset(sum,0,sizeof(sum)); //初始化
// int row_max=col_max=r; //记录行列下标的最大值 从而后续不用额外判断炸弹范围r是否超过了全范围
while(n>0){ //记录输入
n--;
scanf("%d %d %d",&i,&j,&t);
sum[i+1][j+1]+=t; //因为不同目标可能在同一位置 所以要用sum+=t 而不是sum=t
// row_max=max(row_max,i+1); //更新行列下标最大值
// col_max=max(col_max,j+1);
}
for(i=1;i<=5001;i++){ //计算前缀和 (直接在输入矩阵上操作就行 我一开始用了map记录输入 sum求前缀和 会超内存)
for(j=1;j<=5001;j++){
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+sum[i][j]; //三个矩阵加减 再加上本位置
}
}
int ret=0;
if(r>5001) ret=sum[5001][5001]; //如果炸弹范围大于全范围 则ret必然就是全部价值和 直接初始化为全部价值和即可(不然后续代码无法更新ret)
//用这个来更新的话 就可以省去上面那句if(r>5001) 但也不省事其实
// for(i=r;i<=row_max;i++){
// for(j=r;j<=col_max;j++){
// ret=max(ret,sum[i][j]+sum[i-r][j-r]-sum[i][j-r]-sum[i-r][j]);
// }
// }
for(i=r;i<=5001;i++){ //以[i,j]以右下角 r为边长的矩阵的和(当靠近左、上 边长不够r时 sum本身就已经是该矩阵的值了 不用再算了)
for(j=r;j<=5001;j++){
// sum[i][j]=sum[i][j]+sum[i-r][j-r]-sum[i][j-r]-sum[i-r][j]; //不能用这个更新sum[i][j] 改了前面的 会导致后面的出错 要改的话要从右下角开始改
ret=max(ret,sum[i][j]+sum[i-r][j-r]-sum[i][j-r]-sum[i-r][j]);
}
}
// for(i=5001;i>=r;i--){
// for(j=5001;j>=r;j--){
// sum[i][j]=sum[i][j]+sum[i-r][j-r]-sum[i][j-r]-sum[i-r][j]; //用这个 倒着 更新sum[i][j]才行 因为左上的不用右下的
// ret=max(ret,sum[i][j]);
// }
// }
printf("%d",ret);
return 0;
}