动态规划解题分析报告_第1页
动态规划解题分析报告_第2页
动态规划解题分析报告_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

精心整理动态规划题报告1.最少截系统某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗你说说倒蛮容易本呢?成本是个大问题啊所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统及所能拦截的最大导弹数8389207155300299170158652初次审题，感觉就是要求最长递减子序列的个数，但是又考虑到以下这种情况38920715530029917015865156如果是最长递减子序列，则共需2套系统，按此思路却得出3个子序列，故，此方法不可行。那么，贪心行不行呢？！答案当然是可行。我们将所拥有的系统用一个数组保存下来，每一次导弹来袭都对该数字进行扫描一旦搜索到可用系统就将可行系统中最小的替换如果没有的话，则在该数组增加元素；代码如下：#include<iostream>usingnamespacestd;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]=x;break;}if(j>m)a[++m]=x;}cout<<m<<endl;}return0;}当然，经过后来的讨论发现，此题亦可划归D问题，那么如何用动态规划的思想解决呢？只要找到最长非递减字串就可以达到目的应该求最长不降子列这样的长度才是最少需要的套数因为这个序列中的任何两个导弹都不能共用一个拦截系统其余的导弹都能和这个最长序列中的某个导弹分为同一组。代码如下：#include<string.h>#defineMAX1005intGetMinLengthSub(intpre[MAX],intnum[MAX],intarr[MAX],intn){for(i=n-1;i>=0;i--){max=0;pos=i;if(arr[i]<=arr[j]&&num[j]>max){max=num[j];pos=j;}num[i]=max+1;if(num[i]>f_max)f_max=num[i];}}intmain(){inti,n;

精心整理while(scanf("

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论