这里的数据不需要两个数组,开两个就ME了,从左往右,从上往下直接滚动s数组就行
#include<iostream>
#include<cstring>
using namespace std;
const int N=5050;
int s[N][N];
int main()
{
int N,R;
cin>>N>>R;
int n=R,m=R;
for(int i=0;i<N;i++)
{
int x,y,w;
cin>>x>>y>>w;
x++,y++;
s[x][y]+=w;
n=max(n,x),m=max(m,y);//至少是R*R初坐标
}
//求二维前缀和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
//求边长为R的正方形的最大值
int res=0;
for(int i=R;i<=n;i++)
for(int j=R;j<=m;j++)
res=max(res,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
cout<<res<<endl;
return 0;
}
Orz
为什么把R赋值给m n?大佬讲解一下
好像是因为不这么做的话一开始r可能就会大于一开始枚举大正方形就会不存在枚举的下标
不能 AC
R = min(R,5001);加上这句就可
求解:
下面遍历R -1 正方形,因为边界上的不算,不应该是 s[i - 1][j -1]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]??
下面的边界也不算啊,所以不应该是s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]吗?????
####想成格子就明白了
R <= 10^9 当R大于5050时会Segmentation Fault 呢
看不太懂佴
如果R是大于5050的,你这个岂不是就爆了