資源限制 時間限制：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.uj5u.com/houduan/61742.html
標籤：C++
上一篇：STL中_Rb_tree的探索
下一篇：排兵布陣