炸弹可以摧毁边长为R的正方形内部的所有目标,不包括边,\(n\)个目标,每个目标有一个价值,爆炸范围必须与\(x,y\)轴平行,求正方形最大包含的价值数
预处理二维前缀和,从边长允许的范围内开始枚举,取最大值即可,题目要求不能将边上的计算,枚举\((R-1)\times (R-1)\)的正方形即可,认为在坐标系中所有点的坐标都+0.5
#include<bits/stdc++.h>
using namespace std;
const int N=5100;
int n,r;
int s[N][N];
int max_x,max_y;
int main(){
cin>>n>>r;
max_x=max_y=r;
while(n--){
int x,y,w;
cin>>x>>y>>w;
x++;
y++;
s[x][y] +=w;
max_x=max(x,max_x);
max_y=max(y,max_y);
}
for(int i = 1; i <= max_x; i++)
for(int j = 1; j <= max_y; j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
int ans=0;
for(int i = r; i <= max_x; i++)
for(int j = r; j <= max_y; j++)
ans=max(ans , s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r]);
cout<<ans<<endl;
}
原文:https://www.cnblogs.com/hhyx/p/12963799.html