文档介绍：拦截导弹某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段。所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算这套系统最多能拦截多少导弹。输入:导弹数n和n颗依次飞来的高度(1≤n≤1000)输出:一套系统最多拦截的导弹数best,并依次列出被拦截导弹的序号题解有的试题不仅要求输出最优解,而且还要求输出最优解的形成过程。为此,我们设置了一张记忆表,在按自下而上方式求解的过程中,将每一个子问题的最佳决策保存起来,避免在输出方案时重复计算。按照最优解的结构设计状态转移方程一套系统拦截导弹的问题本质是在一个数列中寻求递减的、未必连续的最长子序列。我们从导弹n出发,反序计算被拦截的导弹。设h[i]——导弹i‥导弹n中可被拦截的最多导弹数(包括拦截导弹i)(1≤i≤n)。显然h[i]={h[j]|导弹j的高度≤导弹i的高度}+1;一套系统拦截的最多导弹数best={h[i]}w[i]——记忆表,即最佳方案中导弹i和导弹w[i]相继被拦截(1≤i≤w[i]≤n)显然,h[i]=h[w[i]]+1;one—最佳方案中被拦截的第一枚导弹序号,即best=h[one]=;由上述状态转移方程可知,拦截导弹问题具备了最优子结构性质(要使h[i]最大,子问题的解h[j]必须最大(i+1≤j≤n))和重迭子问题的性质(为求得h[i],必须一一查阅子问题的解h[i+1]‥h[n]),因此可采用动态程序设计的方法求解。按照自下而上的方式计算当前系统拦截的最多导弹数由上述状态转移方程的定义可知阶段i:由右而左计算导弹n-i+1‥导弹n中可拦截的最多导弹数(1≤i≤n);状态k:在阶段i中,当前序列首枚导弹的序号k(k=n-i+1,1≤k≤n)。由于每个阶段中仅一个状态,因此可通过一重循环“fori←ndownto1do”枚举每个阶段的状态i;决策j:在拦截导弹i之后应拦截哪一枚导弹可使得h[i]最大(i+1≤j≤n),即决策w[i];由此得出程序流程:best←0; {初始化}fillchar(h,sizeof(h),0);fillchar(w,sizeof(w),0);fori←ndownto1do {枚举每一个阶段的状态}beginh[i]←1;w[i]←i; {设导弹i被拦截}forj←i+1tondo