激光炸弹

题目 激光炸弹

思路分析

这题恶心在于空间控制严格

只会出现在xy位置 xy为0~5000 所以矩阵范围N开5010即可

直接在原数组上做前缀和 省空间

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=5010;

int s[N][N];

int n,r;

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n>>r;

    r=min(r,5001);

    for(int i=1;i<=n;i++){

        int x,y,w;cin>>x>>y>>w;

        s[x+1][y+1]+=w;//偏移一位 从1开始

    }

    for(int i=1;i<=5001;i++)

        for(int j=1;j<=5001;j++)

            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];

    int x1,y1,x2,y2;

    int res=-1;

    for(int x2=r;x2<=5001;x2++){

        for(int y2=r;y2<=5001;y2++){

            x1=x2-(r-1),y1=y2-(r-1);

            res=max(res,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);

        }

    }

    cout<<res<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 来骗 🏠 00-刷题理模型 ➡️ 蛋糕游戏