用动态规划实现导弹拦截 某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
) `6 R8 o! N* e 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,并依次输出被拦截的导弹飞来时候的高度。! f3 z6 x+ R- E8 L5 L3 F% Z3 G. ~; Y
SAMPLE INPUT:% m% v1 h! B6 v" L" U
389 207 155 300 299 170 158 65
: s3 z% u' U) O# L+ p# N6 K SAMPLE OUTPUT:
' ~9 O# ^- c& e4 Q 6
2 t: \6 {6 y: z2 e6 v 389 300 299 170 158 653 d' P9 B5 X6 z) @, f' H
因为只有一套导弹拦截系统,并且这套系统除了第一发炮弹能到达任意高度外,以后的每一发炮弹都不能高于前一发炮弹的高度;所以,被拦截的导弹应该按飞来的 高度组成一个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数,并依次输出被拦截导弹的高度,实际上就是要求我们在导弹依次飞来的高度序列中寻找 一个最长非递增子序列。+ [5 f% b) q6 \6 k' U9 G# R
设 X={x 1 ,x 2 ,…,x n } 为依次飞来的导弹序列, Y={y 1 ,y 2 ,…,y k } 为问题的最优解(即 X 的最长非递增子序列), s 为问题的状态(表示导弹拦截系统当前发送炮弹能够到达的最大高度,初值为 s=∞—— 第一发炮弹能够到达任意的高度)。如果 y 1 =x 1 ,即飞来的第一枚导弹被成功拦截。那么,根据题意“每一发炮弹都不能高于前一发的高度”,问题的状态将由 s=∞ 变成 s≤x 1 ( x 1 为第一枚导弹的高度);在当前状态下,序列 Y 1 ={y 2 ,…,y k } 也应该是序列 X 1 ={x 2 ,…,x n } 的最长非递增子序列(大家用反证法很容易证明)。也就是说,在当前状态 s≤x 1 下,问题的最优解 Y 所包含的子问题(序列 X 1 )的解(序列 Y 1 )也是最优的。这就是拦截导弹问题的最优子结构性质。
% F, M: @* Q# ^% X/ ~ 设 D(i) 为第 i 枚导弹被拦截之后,这套系统最多还能拦截的导弹数(包含被拦截的第 i 枚)。我们可以设想,当系统拦截了第 k 枚导弹 x k ,而 x k 又是序列 X={x 1 ,x 2 ,…,x n } 中的最小值,即第 k 枚导弹为所有飞来的导弹中高度最低的,则有 D(k)=1 ;当系统拦截了最后一枚导弹 x n ,那么,系统最多也只能拦截这一枚导弹了,即 D(n)=1 ;其它情况下,也应该有 D(i)≥1 。; g: Z3 j: z, j2 e& ^/ w
假设系统最多能拦截的导弹数为 dmax (即问题的最优值),则 dmax = max(D(i)) |