这道题怎么做，涉及最长不下降子序列的最小的分划的

来源：百度知道 编辑：UC知道 时间：2024/06/20 03:44:49
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入数据为两行，
第一行为导弹的数目N
第二行导弹依次飞来的高度，所有高度值均为不大于30000的正整数。

输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开.

样例输入：
8
389 207 155 300 299 170 158 65

样例输出：
6 2

主要是第二问，第一问不用说，已经会做了。
时间限制一秒钟，n<=500。
所有用递归的、求一次删一次的、不懂得最长不下降子序列的最小的分划是什么意思的、不懂得动态规划是什么东西的，都是错的。

不会用动态规划的，都是SB

第一问都会了第二问那不超Easy啊……算法描述如下：

(1)获得输入序列，置共需系统套数为0
(2)计算当前序列最大拦截数，同时记录被拦截的导弹序号，所需系统套数增1。
(3)从当前序列中删除被拦截的导弹序号，形成新序列
(4)判断新序列长度是否为0，是则转(5)，否则转(2)
(5)输出最大拦截数和所需系统数，结束。

当然这样算可以效率稍微低一点，因为上一轮的计算信息没有充分利用，你可以尝试再优化~~

我先做个前提假设： 如果依据后面导弹设立的系统不能再去拦截 前面的导弹
说明白点 就是放过的导弹就不能拦截了

依据上面的前提我们分析下：

比如导弹

A B C D E F G……

很明显 A必须是第一个系统基准高度 我们计数器count=1，并且设置变量max=A；

继续读取数据 如果遇到某个数据大于max，比如C，我们改变max=C，然后count++；

继续读取数据 如果遇到数据大于max，比如F ,我们改变max=F,然后count++;

………………

一直循环到没有数据。

可以得到 这其实就是一直再寻找一组数据中的过程中的最大数并且计数的问题 。
例子:

5 3 6 8 7 2 1

首先 max= 5 count=1 ;
max= 6 count=2 ;
max= 8 count=3 ;
至少3个系统。

恩 我是这么想的 不知道对不对 至于“最长不下降子序列的最小的分划的”我没听过= =！！ 不太懂

PS：
通过你的例子 我可以认为是不能拦截前面的导弹 因为如果拦截了 389 再拦截 300 再回头拦截的话 其实任何状态只要1个系统就可以了 所以。。。。
不过估计也有瑕疵。

用递归算吧 如果不考虑时间空间代价的话