AcWing 99. 激光炸弹
原题链接
简单
作者:
骄骄是骄傲的骄骄
,
2022-02-16 16:43:16
,
所有人可见
,
阅读 176
/*
实际上,就是求二维区间的和
而二维区间的大小是 r*r
把目标看成点,r=1 能覆盖 1*1 1个点
r=2 能覆盖 2*2 4个点
同时做一个坐标偏移,使坐标从 1 开始计算
想用半径为 1 的炸弹炸 (x,y) 坐标
g[x][y]-g[x-1][y]-g[x][y-1]+g[x-1][y-1]
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5010;
int g[N][N];
int main(){
int n, r;
cin>>n>>r;
// x 或 y 的最大值
int M=-1;
for(int i=1; i<=n; i++){
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
M=max(M, x+1); // 为方便计算,做一个偏移
M=max(M, y+1);
g[x+1][y+1]+=w; // 坐标赋值
}
// 如果爆炸半径覆盖所有目标,更新爆炸半径为最大坐标
r=min(r, M);
// 计算前缀和
for(int i=1; i<=M; i++)
for(int j=1; j<=M; j++)
g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
// 最大伤害
int res=0;
for(int i=r; i<=M; i++)
for(int j=r; j<=M; j++)
res=max(res, g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);
/*
for(int i=1; i<=M-r+1; i++)
for(int j=1; j<=M-r+1; j++)
res=max(res, g[i+r-1][j+r-1]-g[i-1][j+r-1]-g[i+r-1][j-1]+g[i-1][j-1]);
*/
cout<<res<<endl;
return 0;
}