每日算法打卡：激光炸弹 day 8

原题链接

99. 激光炸弹

题目难度：简单

题目来源：《算法竞赛进阶指南》, HNOI2003

题目描述

地图上有 N 个目标，用整数 $X_i,Y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含$R\times R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x，y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。

接下来 N 行，每行输入一组数据，每组数据包括三个整数 $X_i,Y_i,W_i$，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

$0 \le R \le 10^9 $
$0<N\le 10000$,
$0\le X_i,Y_i\le 5000$
$0\le W_i\le 1000$

输入样例：

2 1
0 0 1
1 1 1 

输出样例：

1 

题目分析

题目就是说在一个网格区域内放一定数量的炸弹，每个炸弹可以摧毁一个正方形区域的范围，问最多可以摧毁多少价值的目标

那其实把这个问题抽象出来就是，在一个大矩阵中，取出边长为R的正方形，求这个正方形内总价值的最大数目

那么这里的关键问题就是如何去求这个最大值，暴力一点的做法就是依次枚举取最大值

这里就需要使用到我们之前做的二维前缀和的知识，快速求正方形内的价值总和

那么我们枚举的时候，因为边长R是固定的，所以只需要枚举正方形的右下角的坐标即可，例如枚举到（i，j）时，左上角的坐标应该是（i-R+1,j-R+1）

带入我们之前的公式，就可以得到正方形内的价值总和是

$res=S_{i,j}?S_{i?R,j}?S_{i,j?R}+S_{i?R,j?R}$

因为这里的棋盘大小没有特别大，因此时间复杂度也是可以过的

示例代码

#include<iostream>
using namespace std;

const int N = 5010;

int n, m; // 边界的最大值，棋盘大小
int pre[N][N]; // 这里我们为了防止内存超限，只使用一个前缀和数组，先存入数据，再进行计算即可

int main()
{
    int cnt, R;
    cin >> cnt >> R;
    R = min(5001, R); // 因为当R大于棋盘大小时，最大目标值一定是所有价值的总和

    n = m = R; // n和m至少要是R的大小，之后对标记点输入的时候会进行更新

    // 数据读入
    while (cnt--)
    {
        int x, y, w;
        cin >> x >> y >> w;
        x++, y++; // 为求前缀和做预处理，防止数组越界
        n = max(x, n);
        m = max(y, m);
        pre[x][y] += w;
    }

    // 前缀和
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }

    // 枚举边长为R的矩形，取最大值
    int res = 0;
    for (int i = R; i <= n; i++)
    {
        for (int j = R; j <= m; j++)
        {
            res = max(res, pre[i][j] - pre[i - R][j] - pre[i][j - R] + pre[i - R][j - R]);
        }
    }
    cout << res << '\n';
    return 0;
}