题目描述

给出1-n的两个排列P1和P2，求它们的最长公共子序列。

输入输出格式

输入格式：

第一行是一个数n，

接下来两行，每行为n个数，为自然数1-n的一个排列。

输出格式：

一个数，即最长公共子序列的长度

输入输出样例

输入样例#1： 复制

5

3 2 1 4 5

1 2 3 4 5

输出样例#1： 复制

3

说明

【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

---

把第一个串和第二个串的位置进行匹配，然后就转化乘找最长上升子序列

---

#include
    
     #include
     
      using namespace std;int i,m,n,j,k,a[1000001],b[1000001],c[1000001],ans;void add(int x,int z){    for(int i=x;i<=n;i+=i & -i) c[i]=max(c[i],z);}int find(int x){    int ans=0;    for(int i=x;i>0;i-=i&-i) ans=max(ans,c[i]);    return ans;}int main(){    scanf("%d",&n);    for(i=1;i<=n;i++) scanf("%d",&k), a[k]=i;    for(i=1;i<=n;i++) scanf("%d",&k), b[i]=a[k];    for(i=1;i<=n;i++)    {        k=find(b[i])+1;        ans=max(ans, k);        add(b[i],k);    }    printf("%d",ans);}