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

2024-01-08 13:29:12

原题链接

99. 激光炸弹

题目难度:简单

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

题目描述

地图上有 N 个目标,用整数 X i , Y i X_{i}, Y_{i} Xi?,Yi? 表示目标在地图上的位置,每个目标都有一个价值 W i W_i Wi?

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

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

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

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

输入格式

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

接下来 N 行,每行输入一组数据,每组数据包括三个整数 X i , Y i , W i X_{i}, Y_{i}, W_{i} Xi?,Yi?,Wi?,分别代表目标的 x 坐标,y 坐标和价值,数据用空格隔开。

输出格式

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

数据范围

$0 \le R \le 10^9 $
0 < N ≤ 10000 0 < N \le 10000 0<N10000,
0 ≤ X i , Y i ≤ 5000 0 \le X_{i}, Y_{i} \le 5000 0Xi?,Yi?5000
0 ≤ W i ≤ 1000 0 \le W_i \le 1000 0Wi?1000

输入样例:
2 1
0 0 1
1 1 1 
输出样例:
1 

题目分析

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

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

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

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

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

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

r e s = S i , j ? S i ? R , j ? S i , j ? R + S i ? R , j ? R res = S_{i,j} - S_{i-R,j} - S_{i,j-R}+S_{i-R,j-R} res=Si,j??Si?R,j??Si,j?R?+Si?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;
}

文章来源:https://blog.csdn.net/ye_yumo/article/details/135454614
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。