---
title: "激光炸弹"
created: 2025-11-28
tags:
  - 算法
---

# 激光炸弹

## 题目 [激光炸弹](https://www.acwing.com/problem/content/description/101/)

![[image-880f33a9.png]]

## 思路分析

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

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

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

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[蛋糕游戏|蛋糕游戏]]