AcWing 99. 激光炸弹
原题链接
简单
作者:
Rhett
,
2021-01-23 17:32:28
,
所有人可见
,
阅读 3
point
- R可能大于矩阵边长
- 输入矩阵的坐标从0开始,前缀和最好从1开始
- 不同目标可能在同一位置
C++ 代码
#include <iostream>
using namespace std;
const int N = 5010;
int a[N][N];//, s[N][N];
int main(){
int n ,r, w;//坑:R>矩阵边,所以有maxx=maxy=r
int maxx = 0, maxy = 0, maxw = 0;
scanf("%d%d", &n, &r);
maxx = r, maxy = r;
for(int i = 1; i <= n; i++){
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
x++, y++;//从1开始
a[x][y] += w;//错:a[x][y] = w
if(x > maxx) maxx = x;
if(y > maxy) maxy = y;
}
for(int i = 1; i <= maxx; i++){
for(int j = 1; j <= maxy; j++){
//s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
}
for(int i = r; i <= maxx; i++){
for(int j = r; j <= maxy; j++){
w = a[i][j] - a[i - r][j] - a[i][j - r] + a[i - r][j - r];
if(w > maxw) maxw = w;
}
}
printf("%d", maxw);
return 0;
}