本文主要是介绍最长单调递减子序列（非严格单调） 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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
