Longest Ordered Subsequence
搬中文
Descriptions:
給出一個序列，求出這個序列的最長上升子序列，
序列A的上升子序列B定義如下：
- B為A的子序列
- B為嚴格遞增序列
Input
第一行包含一個整數n，表示給出序列的元素個數，
第二行包含n個整數，代表這個序列， 1 <= N <= 1000Output
輸出給出序列的最長子序列的長度，
Sample Input
7 1 7 3 5 9 4 8
Sample Output
4
題目鏈接：
https://vjudge.net/problem/POJ-2533
就是最長子序列，沒啥說的，簡單dp
二分查找的函式有 3 個：
lower_bound(起始地址，結束地址，要查找的數值) 地址：前閉后開，回傳的是第一個大于或等于數值出現的位置，如果數值大于陣列中全部元素，回傳的是結束地址，
upper_bound(起始地址，結束地址，要查找的數值) 地址：前閉后開，回傳的是第一個大于數值出現的位置，如果數值大于陣列中全部元素，回傳的是結束地址，
binary_search(起始地址，結束地址，要查找的數值) 回傳的是是否存在這么一個數，是一個bool值，
AC代碼
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x, y) memset(x, y, sizeof(x)) #define Maxn 1000+10 using namespace std; int dp[Maxn]; int a[Maxn]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int len=1;//最長子序列長度 dp[1]=a[1]; for(int i=2;i<=n;i++) { if(a[i]>dp[len])//大于前一個，則賦值 dp[++len]=a[i]; else { //小于，則找到第一個大于a[i]的值，并把它替代了 int t=lower_bound(dp+1,dp+len,a[i])-dp; dp[t]=a[i]; } } cout<<len<<endl; return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/206283.html
標籤：其他
下一篇：左旋轉字串