AcWing 99. 激光炸弹
原题链接
简单
作者:
Bear_King
,
2021-01-11 12:02:34
,
所有人可见
,
阅读 333
二维前缀和解法
本题难点:边界的划分和限制,以及错位来增加R*R的有效点覆盖
预处理推导公式:s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j];//这两个数组可以合并优化空间
求解边长为R的正方形面积框点公式:s[i][j] - s[i-R][j] - s[i][j-R] + s[i-R][j-R]
#include<iostream>
using namespace std;
const int N = 5010;
int s[N][N];
int n,m;
int main()
{
int cnt , R;
cin>>cnt>>R;
R = min(5010,R);//限制R便于操作,因为R无限大能操作的跟R没区别
n = m = R;//保证右下角存在
while(cnt --)
{
int x,y,w;
cin>>x>>y>>w;
//把输入的坐标都+1,便于前缀和操作,防止数组越界
x ++ , y ++;
//把地图上的点的边界更新成最大
n = max(n,x);
m = max(m,y);
//注意每个点的价值要累加
s[x][y] += w;
}
//预处理地图上所有点的价值->前缀和
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];//对每一个右下角以上的矩阵做前缀和处理
int res = 0;
//枚举所有边长为R的矩形,且(i,j)为每个矩形的右下角坐标,而且初始都从R开始
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;
}