题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。
输入输出格式
输入格式：
第一行是一个数n，
接下来两行，每行为n个数，为自然数1-n的一个排列。
输出格式：
一个数，即最长公共子序列的长度
输入输出样例
说明
【数据规模】
对于50%的数据，n≤1000
对于100%的数据，n≤100000
首先把第一个序列里面的数在第二个序列里面对应hash一下
然后就转化成了求最长上升子序列的问题
对于这种问题，可以用二分查找处理
每次找出大于等于他的第一个位置
替换即可
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=;
inline int read()
{
char c=getchar();int x=,f=;
while(c<''||c>'') {if(c=='-')f=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-,c=getchar();return x*f;
}
int a[MAXN];
int b[MAXN];
int ans[MAXN],tot=;
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{int p=read();
a[p]=i;}
for(int i=;i<=n;i++)
{int p=read();
b[i]=a[p];}
for(int i=;i<=n;i++)
{
int p=lower_bound(ans+,ans+tot+,b[i])-ans;
ans[p]=b[i];
if(p==tot+) tot++;
}
printf("%d",tot);
return ;
}