(BZOJ1218)激光炸弹

喜欢ヅ旅行 2022-01-22 09:23 183阅读 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 条评论，183人围观）

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

相关阅读

相关激光雷达

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

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

相关 poj1218

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

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

相关激光炸弹 - 前缀和

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

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

相关 Binary Bomb 二进制炸弹

实验报告实验（三）题目 Binary Bomb 二进制炸弹　　　计算机科学与技术学院目录第1章实验基本信息... - 3 - 1.1 实

￡神魔★判官ぃ/ 2022年04月22日 20:14/ 0 赞/ 445 阅读

相关 [1218] You are my brother

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

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

相关 (BZOJ1218)激光炸弹

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

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

相关 UVA - 1218 Perfect Service (树形dp)

题意：有n台电脑，互相以无根树的方式连接，现要将其中一部分电脑作为服务器，且要求每台电脑必须连接且只能连接一台服务器(不包括作为服务器的电脑)，求最少需要多少台电脑作为服务器

柔光的暖阳◎/ 2021年12月18日 08:05/ 0 赞/ 161 阅读

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

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

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

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

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

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

相关 linux fork炸弹

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

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