(BZOJ1218)激光炸弹

喜欢ヅ旅行 2022-01-22 09:23 225阅读 0赞

题目链接：[https://www.acwing.com/problem/content/101/][https_www.acwing.com_problem_content_101]

本题考察的主要知识点是二维前缀和的应用。  
我们可以很明显得到一个推导公式：  
s\[i\]\[j\] = s\[i-1\]\[j\] + s\[i\]\[j-1\] －s\[i-1\]\[j-1\] + a\[i\]\[j\];  
这个推导公式很容易就可以得到。所以可以在N^2的时间内得到二维数组的前缀和。  
然后在枚举每个R长度的正方形即可。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int N,R;
    int s[5010][5010];
    
    int main()
    {
        scanf("%d%d",&N,&R);
        for(int i = 1; i <= N; i ++)
            {
                 int x,y,weight;
                 scanf("%d%d%d",&x,&y,&weight);
                 x ++; y ++;//题目的数据范围是从0开始的。我这里是从1开始的，所以需要加1；
                 s[x][y] = weight;
            }
        for(int i = 1; i <= 5008; i ++)
            for(int j = 1; j <= 5008; j ++)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
        int maxx = 0;
        for(int i = R; i <= 5008; i ++)
        {
            for(int j = R; j <= 5008; j ++)
                {
                    int ans = s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R];
                    maxx = max(maxx,ans);
                }
        }
        printf("%d\n",maxx);
    }

[https_www.acwing.com_problem_content_101]: https://www.acwing.com/problem/content/101/

发表评论取消回复

表情：

评论列表（有 0 条评论，225人围观）

还没有评论，来说两句吧...

相关阅读

相关数字炸弹游戏

你输入一个，如果不是爆炸数字，让电脑也要输入一个在缩小范围之后的任意数，如果电脑输入不对，缩小范围然后你再次输入，直到输入正确为止， import random

╰+哭是因爲堅強的太久メ/ 2023年06月25日 03:01/ 0 赞/ 15 阅读

相关激光雷达

1. 激光雷达作用环境探测、测量建图、导航、避障激光雷达是一种用于获取精确位置信息的传感器，犹如人类的眼睛，可以确定物体的位置、大小等，由发射系统、接收系统及信息处理三

你的名字/ 2022年11月15日 11:19/ 0 赞/ 244 阅读

相关 POJ 1218

网络上有一种是发现打开门的规律，然后用数学的方法来解决的，但是一般发现比较困难。所以用了模拟的方法模拟器过程，用数组代表门的状态。 package test; im

古城微笑少年丶/ 2022年09月29日 06:02/ 0 赞/ 18 阅读

相关 poj1218

include<stdio.h> include<math.h> int main() { int i,n,j,k,

系统管理员/ 2022年06月18日 04:19/ 0 赞/ 127 阅读

相关激光炸弹 - 前缀和

一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。现在地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。激光炸弹

痛定思痛。/ 2022年04月23日 09:32/ 0 赞/ 234 阅读

相关 [1218] You are my brother

\[1218\] You are my brother 时间限制: 1000 ms　内存限制: 131072 K 问题描述 Little A gets

柔情只为你懂/ 2022年02月26日 04:06/ 0 赞/ 145 阅读

相关 (BZOJ1218)激光炸弹

题目链接：[https://www.acwing.com/problem/content/101/][https_www.acwing.com_problem_content_

喜欢ヅ旅行/ 2022年01月22日 09:23/ 0 赞/ 226 阅读

相关 AcWing - 99. 激光炸弹【二维前缀和】题解

目录 1.题目 2.代码 1.题目地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都

一时失言乱红尘/ 2021年07月24日 23:53/ 0 赞/ 398 阅读

相关 AcWing-99. 激光炸弹【二维前缀和】题解

目录 1.题目 2.代码 1.题目地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都

客官°小女子只卖身不卖艺/ 2021年07月24日 21:21/ 0 赞/ 451 阅读

相关 linux fork炸弹

众所周知，bash是一款极其强大的[shell][]，提供了强大的交互与编程功能。这样的一款[shell][shell 1]中自然不会缺少“函数”这个元素来帮助程序进行模块化的

迈不过友情╰/ 2021年06月24日 13:59/ 0 赞/ 378 阅读