洛谷：P1439 【模板】最长公共子序列（普及+/提高，dp基础）-------------lower_bound(),upper_bound(),binary_search()

题目：

分析：基础问题，但大佬提出的这个公共转化为上升的思路真的挺秒的。虽然他的lcs和lis没有搞清楚吧！：

根据数据范围，典型的dp【】【】的最长公共子序列的模板是不能用了。

顺序查找显然超时：

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
map<int,int> m;
int main()
{int n;cin>>n;for(int i=0;i<n;i++){int c;cin>>c;m[c]=i+1;} for(int i=0;i<n;i++){int c;cin>>c;v.push_back(c);}vector<int> v2(v.size(),1);//cout<<v2.size()<<endl;for(int i=1;i<n;i++){for(int j=0;j<i;j++) if(m[v[i]]>m[v[j]]) v2[i]=max(v2[i],v2[j]+1);}cout<<v2[n-1];
}

原来stl有自带的二分搜索函数：lower_bound(),upper_bound(),binary_search()

https://www.cnblogs.com/wkfvawl/p/9475939.html

代码：

#include<bits/stdc++.h>
using namespace std;
int m;
int A[100005];
int D2[100005];
map<int,int> mm;
int main()
{cin>>m;int c;for(int i=1;i<=m;i++) {cin>>c;mm[c]=i;}for(int i=0;i<m;i++){cin>>c;A[i]=mm[c];}D2[0]=A[0];int len1 = 0, len2 = 0;for (int i=1; i<m; i++) {  //从a[2]开始枚举每个数(a[1]已经加进去了)if (D2[len2] < A[i]) D2[++len2] = A[i];  //同上else {int p2 = lower_bound(D2, D2 + len2,A[i]) - D2;D2[p2] = A[i];}}cout<<len2+1;
}