AcWing 99. 激光炸弹 用最大横纵坐标 优化1倍时间
原题链接
简单
作者:
搞不懂
,
2023-11-10 20:33:20
,
所有人可见
,
阅读 61
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int s[N][N];
int main()
{
int n, R;
int x1=0,y1=0; //自己加一个优化 x1,y1,用来求最大的横纵坐标
scanf("%d%d", &n, &R);
R = min(R, 5001);
for (int i = 0; i < n; i ++ )
{
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
x ++, y ++ ; //这里之所以要++是因为,我们在计算二维前缀和的时候
//公式当中有i-1这个式子,所以要确保i>=1
x1=max(x1,x);
y1=max(y1,y);
s[x][y] += w;
}
x1=max(x1,R); //这里我们要确保 坐标横纵坐标要>=R的
y1=max(y1,R);
for (int i = 1; i <= x1; i ++ ) //计算前缀和
for (int j = 1; j <= y1; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
int res = 0;
for (int i = R; i <= x1; i ++ ) //i,j当作是右下角坐标
//i-r+1, j-r+1 作为左上角坐标
for (int j = R; j <= y1; j ++ )
res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
//这里的公式之所以没有i-r-1,是因为i-r+1-1=i-r
printf("%d\n", res);
return 0;
}