【牛客】[HNOI2003]激光炸弹

原题链接：登录—专业IT笔试面试备考平台_牛客网

目录

1. 题目描述

2. 思路分析

3. 代码实现

---

1. 题目描述

2. 思路分析

二维前缀和板题。

注意从（1,1）开始存即可，所以每次输入x,y之后，要x++,y++。

因为m的范围最大为5000，每次又是一个边长为r的正方形，所以先用两重for循环求二维前缀和，再用两重循环（外层循环枚举矩阵右下角横坐标，内层循环枚举矩阵右下角纵坐标）求每个矩阵的和，然后不断更新最大值ans即可。

3. 代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5010;
int a[N][N],pre[N][N];signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,r; cin>>n>>r;while(n--){int x,y,v; cin>>x>>y>>v;x++,y++;a[x][y]+=v;}for(int i=1;i<=5001;i++){for(int j=1;j<=5001;j++){pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];}}int ans=0;for(int i=r;i<=5001;i++){for(int j=r;j<=5001;j++){int x1=i-r+1,y1=j-r+1;int x2=i,y2=j;int tmp=pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];ans=max(ans,tmp);}}cout<<ans<<endl;return 0;
}