动态规划解题报告(1)

《动态规划解题报告(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划解题报告1.最少拦截系统ProblemDescription某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.Input输入若干组数据.每组数据包

2、括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)Output对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统及所能拦截的最大导弹数.SampleInput838920715530029917015865SampleOutput2初次审题，感觉就是要求最长递减子序列的个数，但是又考虑到以下这种情况38920715530029917015865156如果是最长递减子序列，则共需2套系统，按此思路却得出3个子序列，故，此方法不可行。那么

3、，贪心行不行呢？！答案当然是可行。我们将所拥有的系统用一个数组保存下来，每一次导弹来袭，都对该数字进行扫描，一旦搜索到可用系统就将可行系统中最小的替换，如果没有的话，则在该数组增加元素；代码如下：#includeusingnamespacestd;intmain(){intn,i,j,x,m,a[100000];while(cin>>n&&n){a[1]=m=0;for(i=1;i<=n;i++){cin>>x;for(j=1;j<=m;j++)if(x<=a[j]){a[j]

4、=x;break;}if(j>m)a[++m]=x;}cout<#include#defineMAX1005intGetM

5、inLengthSub(intpre[MAX],intnum[MAX],intarr[MAX],intn){inti,j,pos,max,f_max;f_max=1;for(i=n-1;i>=0;i--){max=0;pos=i;for(j=i+1;jmax){max=num[j];pos=j;}num[i]=max+1;pre[i]=pos;if(num[i]>f_max)f_max=num[i];}returnf_max;}in

6、tmain(){inti,n;intarr[MAX];intpre[MAX];intnum[MAX];while(scanf("%d",&n)!=EOF){for(i=0;i