P2280 [HNOI2003]激光炸弹

题目描述

输入输出格式

输入格式:

输入文件名为input.txt

输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 xi,yi ,vi 。

输出格式:

输出文件名为output.txt

输出文件仅有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。

输入输出样例

输入样例#1:

2 1
0 0 1
1 1 1

输出样例#1:

1

居然没有题解,,

这道题目我们可以考虑用二维前缀和解决。

我们用dp[i][j]表示从(1,1)到(i,j)的价值之和,

因为只有5000个点,所以我们可以考虑暴力预处理,、

转移方程:dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j](可以画图理解一下)

然后暴力求结果就好

ans=max(ans,dp[i+r][j+r]-dp[i+r][j]-dp[i][j+r]+dp[i][j]);

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int n,r,dp[5101][5101];
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
11     while(c>='0'&&c<='9')
12     {x=x*10+c-48;c=getchar();}
13     flag==1?n=-x:n=x;
14 }
15 int ans=0;
16 int main()
17 {
18     read(n);read(r);
19     for(int i=1;i<=n;i++)
20     {
21         int x,y,z;
22         read(x);read(y);read(z);
23         dp[x+1][y+1]=z;
24     }
25     for(int i=1;i<=5001;i++)
26         for(int j=1;j<=5001;j++)
27             dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+dp[i][j];
28     for(int i=0;i<=5001-r;i++)
29         for(int j=0;j<=5001-r;j++)
30             ans=max(ans,dp[i+r][j+r]-dp[i+r][j]-dp[i][j+r]+dp[i][j]);
31     printf("%d",ans);
32     return 0;
33 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI派

TensorFlow修炼之道(2)——变量(Variable)

变量(Variable)是 TensorFlow 中程序处理的共享持久状态的最佳方法。与常量不同的时,常量创建后,值便无法更改,但是变量创建后 可以修改。并且修...

35540
来自专栏小二的折腾日记

LeetCode-52-N-Queens-II

只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

6110
来自专栏吴伟祥

UML 类图介绍 转

Unified Modeling Language (UML)又称统一建模语言或标准建模语言,是始于1997年一个OMG标准,它是一个支持模型化和软件系统开发的...

8710
来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

41960
来自专栏数据结构与算法

BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)

Description 由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。 由乃认为玉米田不美,所以她决定出...

33780
来自专栏ACM算法日常

交错字符串(动态规划)- leetcode 97

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

16810
来自专栏二进制文集

LeetCode 动态规划 题目分类汇总

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

38860
来自专栏V站

PHP把二维数组中的值取出组合整一维数组

小伙伴们,之前我们在开发过程中肯定遇到需要把二维数组转换为一维数组的时候,基本上都运用了foreach循环遍历赋值给新数组. 今天这里介绍一个新的方法,通过两个...

20520
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

29320
来自专栏码洞

见缝插针 —— 深入 Redis HyperLogLog 内部数据结构分析

HyperLogLog算法是一种非常巧妙的近似统计海量去重元素数量的算法。它内部维护了 16384 个桶(bucket)来记录各自桶的元素数量。当一个元素到来时...

88820

扫码关注云+社区

领取腾讯云代金券