先看图————
故求二维前缀和的公式为:
$f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]$
求左上角为$(x1,y1)$,右下角为$(x2,y2)$的矩阵和公式为:
$ans=f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]$
回到题目,首先,求一下二位前缀和
再枚举每个能炸到的矩阵,看那个和最大
注意:$R$有可能大于整个矩阵的范围,需要特判
AC代码:
#include<bits/stdc++.h>
using namespace std;
int q[5005][5005],n,r,ans;
int main()
{
cin>>n>>r;
r=min(5001,r);
for(int i=0;i<n;i++)
{
int x,y,w;
cin>>x>>y>>w;
q[++x][++y]+=w;
}
for(int i=1;i<=5001;i++)
for(int j=1;j<=5001;j++)
q[i][j]=q[i-1][j]+q[i][j-1]-q[i-1][j-1]+q[i][j];
for(int i=r;i<=5001;i++)
for(int j=r;j<=5001;j++)
ans=max(ans,q[i][j]-q[i-r][j]-q[i][j-r]+q[i-r][j-r]);
cout<<ans<<endl;
return 0;
}
苣~~~