题目描述
给定一个地图,有n个目标,每个目标的坐标为(a,b),该目标的价值为c,给出一个r,让小可爱求出边长为r的正方形范围内的最大价值总和
样例
2 1
0 0 1
1 1 1
算法1
二维前缀和
时间复杂度 前缀和查询 O(1)
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=5010;
int s[N][N];
int n,r,x,y,w;
int main()
{
scanf("%d%d",&n,&r);
r=min(r,5001);//题目所给r可为1e9 ,x,y最多为5001
int xx=r,yy=r;//r<=xx,yy
while(n--)
{
scanf("%d%d%d",&x,&y,&w);
x++,y++;//下标从1开始
s[x][y]+=w;//不同目标同一位置
xx=max(xx,x),yy=max(yy,y);//最大范围
}
for(int i=1;i<=xx;i++)
for(int j=1;j<=yy;j++)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和公式
int ans=0;
for(int i=r;i<=xx;i++)//从(r,r)开始枚举
for(int j=r;j<=yy;j++)
ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);//正方形的边与x,y轴平行
printf("%d\n",ans);
return 0;
}
1.题目给的r可达1e9,x和y的范围最多为5001,所以最开始给r取min
2.以(r,r)为右下角开始枚举
3.正方形的边与x,y轴平行
模板 _右下角点元素:g[x2][y2]-g[x1-1][y2]-g[x2][y1-1]+g[x1-1][y1-1]
本题 x1=i-r y1=j-r 套入模板还得多减一 即左上角(不包括正方形边)的和,题目中求的是 和xy平行 ,即不能包含正方形的边长的正方形范围 所以得加回1
也可以理解为r=r-1
昨日取max时犯了一个大错误,没有让它迭代更新,啊啊啊~下次不会了