【算法】激光炸弹(二维数组前缀和)

这篇具有很好参考价值的文章主要介绍了【算法】激光炸弹(二维数组前缀和)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

地图上有 N 个目标,用整数 Xi,Yi 表示目标在地图上的位置,每个目标都有一个价值 Wi。

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

0 ≤ R ≤ 1e9
0 < N ≤ 10000
0 ≤ Xi , Yi ≤ 5000
0 ≤ Wi ≤ 1000

输入样例

2 1
0 0 1
1 1 1

输出样例

1

思路

         本题用到了前缀和的思想,我们可以先将目标储存到地图中,然后计算点(0,0)到点(xi,yi)为矩形的面积中的目标价值总和,记录到g[xi][yi]中,公式如下:

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

        使用g[ ][ ]数组的时候,只需求出面积为(r - 1)*(r - 1)的正方形中目标价值总和,公式如下:

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

代码 

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n,r,ans;
int g[N][N];

int main()
{
    cin >> n >> r;
    // 将n个目标输入地图之中
    while(n --)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[++ a][++ b] += c;
    }
    // 求二维数组的前缀和
    for(int i = 1; i < N; i ++)
    {
        for(int j = 1; j < N; j ++)
        {
            g[i][j] = g[i][j] + g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        }
    }
    // 暴力求解,找出所有区域价值的最大值
    for(int i = 1; i < N; i ++)
    {
        for(int j = 1; j < N; j ++)
        {
            int a = i - r; if(a < 0) a = 0;
            int b = j - r; if(b < 0) b = 0;
            int sum = g[i][j] - g[a][j] - g[i][b] + g[a][b];
            ans = max(ans,sum);
        }
    }
    cout << ans << endl;
    return 0;
}

题目来自:99. 激光炸弹 - AcWing题库文章来源地址https://www.toymoban.com/news/detail-823813.html

到了这里,关于【算法】激光炸弹(二维数组前缀和)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构实验之矩阵的运算器(二维数组)

    实验目的 掌握并学会运用数组及相关知识 掌握矩阵相关运算的代码实现 学会小组的分工与合作 体会封装的好处 实验任务及要求 要求实现矩阵的计算器,能供用户选择不同菜单,进而实现不同存储形式及调用相应计算的算法,并记录运算过程。 运算程序主要包括:①矩阵的

    2024年01月15日
    浏览(37)
  • lintcode 1840 · 矩阵还原【中等 vip 二维前缀和数组】

    https://www.lintcode.com/problem/1840

    2024年02月04日
    浏览(44)
  • 【数据结构】二维数组的行优先、列优先存储问题

    今天同学问我一道感觉很基础的数据结构问题,虽然答案做对了,但是原理一直比较迷,仔细看了一下题,原来是自己把自己绕进去了。。。在此记录一下,大佬如果有更好的方法,可以在评论区留言,不定期更新。 先给出行优先和列优先的计算公式: 设数组为A[m][n]( m 行

    2024年02月10日
    浏览(55)
  • 数据结构二维数组计算题,以行为主?以列为主?

    1.假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=(  )。 A.808            B . 818             C.1010             D.1020 答案: B 解释:以行序为主,则 LOC[5,5]=[ ( 5-1 ) *100+ ( 5-1 ) ]*2+10=818 。 2

    2024年02月05日
    浏览(49)
  • 【尚硅谷】数据结构和算法——前缀、中缀、后缀表达式规则

    跟着B站的尚硅谷学习数据结构与算法,语言为java,目前是第七个代码内容——前缀、中缀、后缀表达式 课程传送门:尚硅谷——前缀、中缀、后缀表达式 1)前缀表达式又称波兰式, 前缀表达式 的运算符位于操作符之前。 2)举例说明:(3+4)*5-6 对应的前缀表达式就是 - *

    2024年02月03日
    浏览(60)
  • 数据结构 | 寻找二维数组的最大值和对应下标 | C语言代码

    题目:         本题目要求读入M(最大为10)行N(最大为15)列个元素,找出其中最大的元素,并输出其行列值。 输入格式:         输入在第一行中给出行数m和列数n。接下来输入m*n个整数。 输出格式:         输出最大值的行号,列号,值。 输入样例: 2 3 1 2 3 4 5 6 输

    2024年02月05日
    浏览(53)
  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式,是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式,可以表示为 那么问题就来了,树只是一种抽象的数据

    2024年02月08日
    浏览(47)
  • 一、二维前缀和算法

    一维前缀和: 二维前缀和: 给你一个整数数组 nums ,请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中

    2024年02月16日
    浏览(35)
  • 前缀和算法【一维、二维】

    首先这种算法适合于求 从 x 到 y 的和 。 一维代码十分简单,我们只需要每个都记录前面所有的和即可,注意细节 下标从1开始 这里我们就看两种情况:一种是 开始时 ,一种是 执行中 在开始时,因为我们是从1开始,a[0] = 0,所以第一个就是temp; 在执行过程中,因为前一个是

    2023年04月18日
    浏览(31)
  • 每周一算法:二维前缀和

    对一个序列预处理得到前缀和数组,可以在 O ( 1 ) O(1) O ( 1 ) 的时间复杂度计算序列中任意区间的元素之和,这是前缀和算法的作用。而二维前缀和是用来优化处理子矩阵的和。 例如,对于矩阵 A = [ 1 4 5 2 9 5 2 1 6 9 8 3 4 2 1 6 ] A=left[ begin{matrix}1 4 5 2\\\\ 9 5 2 1 \\\\ 6 9 8 3 \\\\ 4 2 1 6en

    2024年02月06日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包