Longest Ordered Subsequence
搬中文
Descriptions:
给出一个序列，求出这个序列的最长上升子序列。
序列A的上升子序列B定义如下：
Input
第一行包含一个整数n，表示给出序列的元素个数。
Output
输出给出序列的最长子序列的长度。
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; }
【POJ - 2533】Longest Ordered Subsequence （最长上升子序列 简单dp）
原文：https://www.cnblogs.com/sky-stars/p/12367682.html