算法训练 拦截导弹(最长递增子序列和最长递减子…
2020-02-20 16:01:04来源:博客园 阅读 ()
算法训练 拦截导弹(最长递增子序列和最长递减子序列问题,输入回车时停止输入)
资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 输入格式 一行,为导弹依次飞来的高度 输出格式 两行,分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数 样例输入 389 207 155 300 299 170 158 65 样例输出 6
2 算法优化: 从可变长数列最初开始,如果当前数大于现有可变长上升子序列最后一个值,那么直接把它添加到上升子序列的末尾;但如果它小于最后一个数值,那么就从现有上升子序列的开始判断,代替掉第一个比它大的值,这样使得的上升子序列会在保证最长的前提下,保持每个数都是最小,保证后来的数最大可能进入序列,保证最长 代码如下: 方便交流学习
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 //author:zq 5 //最长递增子序列 6 int addLong(vector<int>obj){ 7 vector<int>result; 8 result.push_back(obj[0]); 9 vector<int>::iterator it; 10 for(it=obj.begin()+1;it!=obj.end();it++){ 11 if(*it>result[result.size()-1]){ 12 result.push_back(*it); 13 }else{ 14 for(int i=0;i<result.size();i++){ 15 if(*it<result[i]){ 16 result[i]=*it; 17 break; 18 } 19 } 20 } 21 } 22 return result.size(); 23 } 24 25 //最长递减子序列 26 int minLong(vector<int>obj){ 27 vector<int>result; 28 result.push_back(obj[0]); 29 vector<int>::iterator it; 30 for(it=obj.begin()+1;it!=obj.end();it++){ 31 if(*it<result[result.size()-1]){ 32 result.push_back(*it); 33 }else{ 34 for(int i=0;i<result.size();i++){ 35 if(*it>result[i]){ 36 result[i]=*it; 37 break; 38 } 39 } 40 } 41 } 42 return result.size(); 43 } 44 // cout<<result.size(); 45 int main(){ 46 vector<int>objs; 47 int p; 48 char s; 49 while(s!='\n'){ 50 cin>>p; 51 s=getchar(); 52 objs.push_back(p); 53 } 54 int max,min; 55 max=addLong(objs); 56 min=minLong(objs); 57 cout<<min<<endl<<max; 58 return 0; 59 }
原文链接:https://www.cnblogs.com/zq-dmhy/p/12336789.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:STL中_Rb_tree的探索
下一篇:排兵布阵
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash