激光炸弹 刷题笔记

前置知识 二维前缀和

子矩阵的和 刷题笔记 {二维前缀和}-CSDN博客

思路  参考二维前缀和
将子矩阵的和 做成动态矩阵
一个个矩阵搜索 符合要求边长 矩阵中的元素和最大值
将x1,y1用i-k,j-k表示即可 
x2,y2用i，j表示

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N =5050;

int s[N][N];
int n,k,m,cnt;
int temp=0;
int main(){
    cin>>cnt>>k;
    //k=min(5001,k);
    //n=m=k;
    for(int i=0;i<cnt;i++){
        int x,y,w;
        cin>>x>>y>>w;
        x++;
        y++;
        s[x][y]+=w;
         n=max(n,x);
         m=max(m,y);
        
        
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+s[i][j];
        }
    }
    int ans=0;
    for(int i=k;i<=n;i++){
        for(int j=k;j<=m;j++){
            //s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
            temp=s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k];
        //    cout<<i-1<<' '<<j-1<<endl<<i-k<<' '<<j-1<<endl<<i-1<<' '<<j-k<<endl<<i-k<<' '<<j-k<<endl<<endl;
            //cout<<temp<<endl;
            if(temp>ans){
                ans=temp;
            }
             //cout<<"s i-1 j-1  "<<s[i-1][j-1]<< " i-1 j-1 "<<i-1<<' '<<j-1<<endl;
            //cout<<"i-1 j-1 "<<i-1<<' '<<j-1<<endl<<"i-k  j-k  "<<i-k<<' '<<j-k<<endl;
        }
    }
    cout<<ans;
    return 0;
}