【【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值的最大值。看不懂？把样例掏出来看看：

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

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

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

依次类推，一直到300，可以得到以下结果：

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

依据这个规律，可以完善整张表格：

我们总结一下，我们确定每一个dp时，先在这个数据后面找到符合条件的其它数据，它们的dp值加上1后与自己当前dp比较，当前dp取大的那个数。那么，动态转移方程就来了！——

为什么要用一个最大值？那是因为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，欢迎指教。愿求高人指点。谢谢！

累死偶咧