洛谷 P2280 [HNOI2003] 激光炸弹

P2280 [HNOI2003] 激光炸弹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路 前缀和? 暴力枚举?

读入数据 枚举每个以i ,j为右下角 长度为m的正方形?

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5001;
int s[5002][5002]={0};
int main(){
?? ?int n,m;
?? ?cin>>n>>m;
?? ?for(int i=1;i<=n;i++){
?? ??? ?int o,j,c;
?? ??? ?cin>>o>>j>>c;
?? ??? ?s[o+1][j+1]+=c;
?? ?}
?? ?
?? ?for(int i=1;i<=N;i++){
?? ??? ?for(int j=1;j<=N;j++){
?? ??? ??? ?s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
?? ??? ??? ?//这里减一了 所以s数组下标要偏移一下 防止0越界访问到-1?
?? ??? ??? ?
?? ??? ?}
?? ?}
?? ?int maxx=0;

?? ?for(int i=m;i<=N;i++){
?? ??? ?for(int j=m;j<=N;j++){
?? ??? ??? ?int temp=s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m];

//这里是二维前缀和的特定范围计算
?? ??? ??? ?maxx=max(maxx,temp);
?? ??? ?}
?? ?}
?? ?cout<<maxx;
?? ?return 0;
}

一开始 re了

后来参考了iMya_nlgau 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大佬 解决了数组空间 和越界访问的问题