【【NOIP1999 普及组】导弹拦截——最长不上升子序列问题】动态规划

本文主要是介绍【【NOIP1999 普及组】导弹拦截——最长不上升子序列问题】动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

声明

作者非职业程序员,本文仅在分享自己的心得,错误较多欢迎指出,各位大佬不喜勿喷

本文采用和作者一样的小白一理解的的Pascal语言

这篇博客同时为了我的一位不懂代码但对算法十分感兴趣的朋友而写,故没有放一些“高级”元素

写得有些草率哈,请谅解:P

一、题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度,计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

 输入格式

一行,若干个整数,中间由空格隔开。

输出格式

两行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入 #1

389 207 155 300 299 170 158 65

输出 #1

6
2

说明/提示

对于前 50%数据(NOIP 原题数据),满足导弹的个数不超过 2000 个。该部分数据总分共 100分。可使用O(n^2)做法通过。

对于后 50%的数据,满足导弹的个数不超过 10^5 个。该部分数据总分也为 100分。请使用O(nlogn) 做法通过。

对于全部数据,满足导弹的高度为正整数,且不超过 5*10^4。

二、题目分析

由题意,由于这套系统后一次的高度不能高于前一次的高度,因此它拦下来的导弹的高度一定是大于等于上一枚。为了要拦截更多的导弹,这个序列应尽可能的长,即找到一个最长不上升子序列

这道题我们用动态规划去解决

1.什么是动态规划dp

在递归中,我们会发现许多点往往会被重复计算,极大地浪费了时间,降低了效率。那么,何不把计算过的点记录下来,减轻下一次的计算量呢?所以,在dp中,我们用一个数组比如说dp(一维或二维)来保存历史记录。

然后再来看看dp的具体思想。——嗯?这不就是数学归纳法吗?

数学归纳法
第一数学归纳法
概念

设 P ( n ) 是 一 个 含 有 正 整 数 n 的 命 题 , 如 果

( 1 ) 当 n = a 时 , P ( a ) 成 立 ;

( 2 ) 由 P ( k ) 成 立 必 可 推 得 P ( k + 1 ) 成 立 ,

那 么 P ( n ) 对 所 有 正 整 数 n ≥ a 都 成 立 。


第二数学归纳法
概念

设 P ( n ) 是 一 个 含 有 正 整 数 n 的 命 题 , 如 果

( 1 ) 当 n = a 时 , P ( a ) 成 立 ;

( 2 ) 在 P ( m ) 对 所 有 适 合 a ≤ m ≤ k 的 正 整 数 m 成 立 的 假 定 下 , P ( k + 1 ) 成 立 ,

那 么 P ( n ) 对 所 有 正 整 数 n ≥ a 都 成 立 。


“跳跃”的数学归纳法
概念

设 P ( n ) 是 一 个 含 有 正 整 数 n 的 命 题 , 如 果

( 1 ) 当 k = 1 , 2 , ⋯ , k 0 时 , 命 题 P ( k ) 是 成 立 的 ;

( 2 ) 由 P ( k ) 成 立 必 可 推 得 P ( k + k 0 ) 成 立 ,

那 么 P ( n ) 对 所 有 正 整 数 n 都 成 立 。

    这个归纳法的起点是一组事实,相当于对所有正整数以 k 0 k_0 k0​ 个为一组的规模 ( 跨度为 k 0 k_0 k0​ ) 进行分组,形成一个分组序列,然后由前一个分组导出后一个分组,不断进行下去,这是分类分组的思想。

 

跷跷板归纳法
概念

设 有 两 个 关 于 正 整 数 n 的 命 题 A n , B n , 如 果

( 1 ) A 1 成 立 ;

( 2 ) 假 设 A k 成 立 , 则 推 出 B k 成 立 ;

( 3 ) 假 设 B k 成 立 , 则 推 出 A k + 1 成 立 ,

那 么 对 于 任 意 正 整 数 n , 命 题 A n , B n 都 成 立 。
反向归纳法
概念

设 P ( n ) 是 与 自 然 数 n 相 关 的 命 题 , 如 果

( 1 ) 存 在 一 个 递 增 的 无 限 自 然 数 序 列 { n k } , 使 命 题 P n k 成 立 ,

( 2 ) 在 假 设 当 n = k + 1 时 命 题 P k + 1 成 立 的 前 提 下 , 当 n = k 时 , P ( k ) 成 立 , 那 么 命 题 P ( n ) 对 所 有 自 然 数 n 都 是 成 立 的 。

 

推广:数学归纳法也可用于实数相关的问题?

    Note : 应以开放的思维看待数学归纳法,学习其思维的精神与本质,而不要被其形式所束缚。

    比如:

设 P ( x ) 是 与 非 负 实 数 相 关 的 命 题 , 如 果

( 1 ) 当 x ∈ [ 0 , 1 ] 时 , P ( x ) 成 立 ;

( 2 ) 在 假 设 P ( x ) 成 立 的 前 提 下 , 可 推 出 P ( x + 1 ) 成 立 ,

那 么 命 题 P ( x ) 对 所 有 非 负 实 数 x 都 是 成 立 的
一些保守的思考与联想

    Note : 数学归纳法本质就是:起点(起始状态) --> 桥梁(状态转移方程) --> 结论(结果),最难的就是“桥梁”的构建与证明。从思维形式上,它有点像算法思维中的“动态规划”法。

End
————————————————
版权声明:本文为CSDN博主「balancscy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/m0_53793870/article/details/122454226

(有删减)

数学归纳法,说白了就是从一个已经证明的中心点出发,通过它他点与中心点的联系,证明其它点,进一步证明整个命题

动态规划呢?它也需要一个中心点(初始值)和一个关系式(动态转移方程)来找到最优解,用一个数组储存值

①.初始值

dp往往把最后一个值设为初始值,因为最后一个值是100%确定的,然后倒着往前推。但也有例外,比如爬楼梯问题

有n阶楼梯,每次只能走一级或两级,求从底部到顶部有几种走法

(我曾因实践这个题目被当成傻子)

这里比如把记录到第i阶楼梯的走法为dp[i],则首先设置dp[1]=1,dp[2]=2,因为之后所有的走法都建立在这两步上。不信?请接着往下看

②.动态转移方程

这是整个dp的核心,用来描述如何从历史记录中得到新结果。通过构建一系列子问题,求解部分子问题,然后通过子问题的依赖关系求解

动态转移方程是动态规划算法中的一个重要概念,用于描述问题的最优解与子问题的最优解之间的关系。在动态规划中,我们通常需要将原问题分解成若干个子问题,然后通过求解子问题的最优解来得到原问题的最优解。动态转移方程就是描述子问题最优解与原问题最优解之间的关系的数学公式。通过动态转移方程,我们可以将问题的求解过程转化为一个递推的过程,从而避免了重复计算,提高了算法的效率。

CSDNAI生成

回到走楼梯的例子,第1、2阶之后,第x阶台阶都可以由它的前一阶走一步和它的前两阶走两步到达,而到达前一阶的方法数储存在dp[x-1]中,到达前两阶都方法数储存在dp[x-2]中,因此,到达第x阶的方法数dp[x]=dp[x-1]+dp[x-2]——这就是动态转移方程

2.回归原题

①.第一问

这道题的动规思路为“逆着看,顺着找”。

一维数组dp[i]用于储存从第i个数据开始的最长不上升子序列长度,每个数组元素被初始化为1,因为最坏情况下,它自己就是一个最长不上升子序列。

而最后一个数据为开始的最长不上升子序列只有一 个,也就是它自己,故起始点dp[n]=1

同时对于每一个dp[i],它的值为它后面所有比它(指输入的数据,下同)小或等于的数据的dp值+1(表示把这个数接上去)的和与它的dp值的最大值。看不懂?把样例掏出来看看:

a[i]38920715530029917015865
dp[i]11111111

倒着看,对158来说,后面的数比它大,以它为开始的最长不上升子序列长度为1,而如果把它加到以65为开始的最长不上升子序列中,长度变为1+1=2,由于2>1,我们选择把它接上去,于是以158为开始的最长不上升子序列长度取2,得到表格:

a[i]38920715530029917015865
dp[i]111111121

再看170,它后面的158、65都比它小,这时“顺着找”最大值,如果将170接在以158为开始的最长不上升子序列的开头,长度变为1+2=3,与不接的1相比,因为1<3,所以将170对应的dp改为3

a[i]38920715530029917015865
dp[i]111111321

顺着找,我们把目光投向65,由于170>65,170也可以接在以65为开始的最长不上升子序列前,这时长度变为1+1=2,可此时我们已经找到了更长的方案——3,因为3>2,所以我们并不打算这么接。最终,以170为开始的最长不上升子序列长度确定为3。

依次类推,一直到300,可以得到以下结果:

a[i]38920715530029917015865
dp[i]11154321

而155呢?它后面比它小或等于的只有65,因为65的dp是1,接上去是2,它自己的dp只有1,因为2>1,所以155的dp更新为2

a[i]38920715530029917015865
dp[i]11254321

依据这个规律,可以完善整张表格:

a[i]38920715530029917015865
dp[i]64254321

我们总结一下,我们确定每一个dp时,先在这个数据后面找到符合条件的其它数据,它们的dp值加上1后与自己当前dp比较,当前dp取大的那个数。那么,动态转移方程就来了!——dp[i]=max(dp[i],dp[j]+1)(1\leqslant i< n,i< j\leqslant n,a[i]\geqslant a[j])

为什么要用一个最大值?那是因为dp[j]+1可能还没有dp[i]大,之前170的例子就能很好的说明这一点。

②.第二问

求最少要几套系统,核心思想是:遍历每个点,如果当前高度大于已知所有系统的最大高度,那就要多一套系统,这套系统的高度就是这个点的高度。第一个系统的高度是a[1]。另外还有一些细节,本人太菜讲不清楚,找一位思想不约而同的大佬的描述:

既然要最少的系统,我们对于每一套系统都要“用干净”,即尽量多次使用,避免浪费。很容易想到用贪心了。每一次从已有的系统里找第一个大于等于当前高度a[i]的系统(一定要用符合条件且最小的,大的要尽量留着给后面用),并更新当前系统的高度。若找不到这样的系统,则需要一个新的系统,并且高度为a[i]。不难发现,存储系统高度的数组也是单调不下降的,因此也可以使用二分优化查询过程。
————————————————
版权声明:本文为CSDN博主「龙星尘」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/wo_ai_luo_/article/details/127310307

三、上代码

program dp_daodanlanjie;
vara,dp,h:array[1..100000] of longint;n,i,j,ans:longint;flag:boolean;
function max(a,b:longint):longint;beginif a>b then exit(a) else exit(b);end;
begin//--------------------------Input------------------------while not(eof) dobegininc(n);read(a[n]);end;//Delete ^Zn:=n-1;//--------------------------The First Question------------------------//Set start dpfor i:=1 to n do dp[i]:=1;//<---for i:=n-1 downto 1 do//--->for j:=i+1 to n do//Search smaller numberif a[j]<=a[i] then//dynamic transfer equationdp[i]:=max(dp[i],dp[j]+1);//Search the biggest onefor i:=1 to n do ans:=max(ans,dp[i]);//First answerwriteln(ans);//--------------------------The Second Question------------------------//At least one systemans:=1;h[1]:=a[1];for i:=2 to n dobeginflag:=false;//"To",NOT "Downto"!for j:=1 to ans do//Is it big enough?if a[i]<=h[j] thenbegin//Reset highth[j]:=a[i];//Have foud one system.flag:=true;//Stop searchingbreak;end;//If flag=false,here needs to add a new systemif flag=false then begin inc(ans);h[ans]:=a[i];end;end;writeln(ans);
end.

输入

389 207 155 300 299 170 158 65 ^Z

输出

6
2

四、结语

动态规划是很重要的算法,极大地提高了程序效率。但需要彻底领悟才能发挥出道道AC的大牛水平。作者新手,若有讲解不当或代码有BUG,欢迎指教。愿求高人指点。谢谢!

累死偶咧

这篇关于【【NOIP1999 普及组】导弹拦截——最长不上升子序列问题】动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/261410

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque