[Leaf] [P2280] 激光炸弹

luogu-p2280-激光炸弹">Luogu-P2280 激光炸弹

1. 核心逻辑

• 问题本质: 在权值分布的二维网格中，寻找固定大小矩形覆盖的最大权值和。

• 破局转换:

  1. 二维前缀和: 利用 $O(RC)$ 的预处理实现 $O(1)$ 的矩形区域和查询。

  2. 坐标偏移: 题目坐标为 $[0, 5000]$，为防止 $i-1$ 越界及处理边界条件，建议统一执行 (x+1, y+1) 映射，将值域平移至 $[1, 5001]$。

  3. 覆盖逻辑: 炸弹覆盖边长为 $M$ 的正方形。由于坐标点在格子中心，其覆盖范围恰好是 $M \times M$ 的格子。

2. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int maxn = 5005;

int n, m;
ll sum[maxn][maxn];

int main( )
{
    ios::sync_with_stdio( 0 );
    cin.tie( 0 );

    cin >> n >> m;
    // 激光炸弹范围限制在题目最大坐标以内
    int limit = 5001;
    for( int i = 1; i <= n; ++ i )
    {
        int x, y, v;
        cin >> x >> y >> v;
        sum[x + 1][y + 1] += v;
    }

    // 1. 构建二维前缀和
    for( int i = 1; i <= limit; ++ i )
    {
        for( int j = 1; j <= limit; ++ j )
        {
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    }

    // 2. 遍历所有可能的爆破点 (i, j) 作为右下角
    ll ans = 0;
    // 若 M 超过 limit，直接覆盖全图
    m = min( m, limit );
    for( int i = m; i <= limit; ++ i )
    {
        for( int j = m; j <= limit; ++ j )
        {
            ll cur = sum[i][j] - sum[i-m][j] - sum[i][j-m] + sum[i-m][j-m];
            ans = max( ans, cur );
        }
    }

    cout << ans << "\n";

    return 0;
}

3. 归档备注

• 易错点: 注意 $M$ 的范围，若 $M=0$ 或 $M$ 极大时的边界处理。

• 维度不变量: 矩形查询公式 sum[i][j] - sum[i-m][j] - sum[i][j-m] + sum[i-m][j-m] 必须熟练掌握。

• 关联知识点: 降维技巧