最长单调递减子序列（非严格单调） uva 231Testing the CATCHER

本文主要是介绍最长单调递减子序列（非严格单调） uva 231Testing the CATCHER，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述： 一个序列seq []，找出一个最长的不严格单调递减的子序列（subseq [i+1] <= subseq [i] ），输出这个子序列的长度

解决1：O（n*n）

令dp [] 数组，dp [i] 表示以seq [i] 为最小元素（也就是子序列中最后一个）的序列的长度，dp []的最大值就是所求结果

伪代码：

  int seq[] , dp[]

  dp[0]  = 1;

 for(i = 1; i < seq.size ; i++){

    dp[i] = 1;

    for(j = 0; j <= i ;j++){

    if(seq[j] >= seq[i] && dp[j] +1 > dp[i])      

            dp[i]  = dp[j] +1;

}

}

                                  

解决2：O（n*n）如果用二分查找可以达到O(n*lgn)

      使用visited[] 记录序列，最后visited[] 的 size 就是结果，这个很神奇！！

以：5  4    6  7  3  4  2 为例看visited[]的变化

i=1       5

i=2      5  4

i=3      5  4  

           6  4  

i=4      6  4

           7  4  

i=5      7  4  3

i=6      7  4   3 

           7   4   4

i=7      7   4   4   2               visited.size = 4  ----->  subseq.size = 4;

我的理解：visited[] 数组并不是记录了满足题意的子序列，但是怎么理解visited[] 的size 就是子序列的长度？

形象的说就是：邪不压正，最长的一个子序列永远不会被比它短的子序列所覆盖掉。先假想visited[] 中已经保存了最长子序列了，那么在修改中间值时，不会把整条子序列都覆盖掉的，因为它不够长。当然，这个最长的任何时候出现都是可以的，总会比其他的序列来的长。

 

WA的教训：输出时最后一组数据之后不要输出空行，否则WA，而且怎么想都想不到。

代码1  和 代码2：

 

//uva 231 Testing the CATCHER
//AC By Warteac 
//2013-4-6
//O(N*N)
//runtime:0.020
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<climits>
using namespace std;
//
class TestingTheCatcher{
private:vector <int> seq;int maxLength;
public:void initial();bool readCase();void computing();void outResult();
};
void TestingTheCatcher::initial(){seq.clear();maxLength = 0;
}
bool TestingTheCatcher::readCase(){int x;initial();if(cin>>x && x==-1){return false;}else{while(x!=-1){seq.push_back(x);cin>>x;}return true;}
}
void TestingTheCatcher::computing(){vector <int> visited;visited.clear();visited.push_back(1);for(int i = 1; i < seq.size(); i++){visited.push_back(1);for(int j= 0; j <i; j++){if(seq[j] >= seq[i] && visited[j]+1 >visited[i]){visited[i] = visited[j] + 1;}}}for(int i = 0; i<visited.size();i++){if(visited[i]>maxLength)maxLength = visited[i];}
}
void TestingTheCatcher::outResult(){cout<<"  maximum possible interceptions: "<<maxLength<<endl;//cout<<endl;
}
/
int main(){TestingTheCatcher tc;int num=0;while(tc.readCase()){num++;tc.computing();if(num>1)cout<<endl;cout<<"Test #"<<num<<":"<<endl;tc.outResult();}return 0;
}

 

//uva 231 Testing the CATCHER
//AC By Warteac
//2013-4-6
//O(N*N)
//runtime:0.012s
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<climits>
using namespace std;
//
class TestingTheCatcher{
private:vector <int> seq;int maxLength;
public:void initial();bool readCase();void computing();void outResult();
};
void TestingTheCatcher::initial(){seq.clear();maxLength = 0;
}
bool TestingTheCatcher::readCase(){int x;initial();if(cin>>x && x==-1){return false;}else{while(x!=-1){seq.push_back(x);cin>>x;}return true;}
}
void TestingTheCatcher::computing(){vector <int> visited;visited.clear();visited.push_back(INT_MAX);int t=0,j=0;for(int i = 0; i < seq.size(); i++){for( j= visited.size()-1; j >= 0; j--){if(seq[i] <= visited[j])break;}t = j+1;if(t >= visited.size()){visited.push_back(seq[i]);}else if(seq[i] > visited[t]){visited[t] = seq[i];}}maxLength = visited.size()-1;
}
void TestingTheCatcher::outResult(){cout<<"  maximum possible interceptions: "<<maxLength<<endl;//cout<<endl;
}
/
int main(){TestingTheCatcher tc;int num=0;while(tc.readCase()){num++;tc.computing();if(num>1)cout<<endl;cout<<"Test #"<<num<<":"<<endl;tc.outResult();}return 0;
}

这篇关于最长单调递减子序列（非严格单调） uva 231Testing the CATCHER的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---