《动态规划解题分析报告.doc》由会员分享，可在线阅读，更多相关《动态规划解题分析报告.doc（3页珍藏版）》请在三一文库上搜索。
1、精心整理动态规划解题报告1.最少拦截系统ProblemDescriptio n 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统但是这种导弹拦截系统有一个缺陷：虽然 它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能超过前一发的高度.某天，雷达捕 捉到敌国的导弹来袭.由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导 弹.怎么办呢？多搞几套系统呗！你说说倒蛮容易，成本呢？成本是个大问题啊.所以俺就到这里来求救了I请帮助计算一下最少需要多少套拦截系统In put输入若干组数据每组数据包括：导弹总个数（正整数）,导弹依此飞来的高度（雷达给出的高度数据 是不大于30000
2、的正整数，用空格分隔）Output对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统及所能拦截的最大导弹数.Sample In put838920715530029917015865SampleOutput2初次审题，感觉就是要求最长递减子序列的个数，但是又考虑到以下这种情况38920715530029917015865156如果是最长递减子序列，则共需 2套系统，按此思路却得出3个子序列，故，此方法不可行。 那么，贪心行不行呢？！答案当然是可行。我们将所拥有的系统用一个数组保存下来，每 一次导弹来袭，都对该数字进行扫描，一旦搜索到可用系统就将可行系统中最小的替换，如果没有 的话，贝
3、U在该数组增加元素；代码如下：#in clude<iostream>usingn amespacestd;in tma in（）精心整理intn,i ,j,x,m,a100000;while(ci n>>n&&n)a1=m=0;for(i=1;i<=n ;i+)cin> >x;for(j=1;jv=m;j+)if(x<=aj)aj=x;break;if(j>m)a+m=x;coutvvmvve ndl;return。；当然，经过后来的讨论发现，此题亦可划归为DP问题，那么如何用动态规划的思想解决呢？只要找到最长非递减字串就可
4、以达到目的。应该求最长不降子列。这样的长度才是最少需要的套数，因为这个序列中的任何两个导弹都不能共用一个拦截系统，而且其余的导弹都能和这个最长序列中的某个导弹分为同一组。代码如下：#in clude<stdio.h>#i nclude<stri ng.h>#defi neMAX1005in tGetMi nLe ngthSub(i ntpreMAX,i ntn umMAX,i ntarrMAX,i ntn)in ti,j,pos,max,f_max;f_max=1;for(i=n-1;i>=0;i-)max=0;pos=i;for(j=i+1;j <n ;j
5、+)if(arri<=arrj &&nu mj>max)max=nu mj;pos=j;nu mi=max+1;prei=pos;if(nu mi>f_max)f_max=nu mi; 一 一returnf_max; _in tma in()in ti, n;in tarrMAX;精心整理in tpreMAX;intnu mMAX;while(sca nf("%d",&n )!=EOF)for(i=0;i <n ;i+)scan f("%d",&arri);prin tf("%dn",GetMi nLe ngthSub(pre, num,arr, n);return。；