题目描述

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

输入输出格式

输入格式：

 

第一行是一个数n，

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

5 3 2 1 4 51 2 3 4 5

输出样例#1： 

3

说明

【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

 

首先把第一个序列里面的数在第二个序列里面对应hash一下

然后就转化成了求最长上升子序列的问题

对于这种问题，可以用二分查找处理

每次找出大于等于他的第一个位置

替换即可

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int MAXN=100001; 6 inline int read() 7 { 8     char c=getchar();int x=0,f=1; 9     while(c<'0'||c>'9')    {
   if(c=='-')f=-1;c=getchar();}10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;11 }12 int a[MAXN];13 int b[MAXN];14 int ans[MAXN],tot=0;15 int main()16 {17     int n;18     scanf("%d",&n);19     for(int i=1;i<=n;i++)    20     {
   int p=read();21     a[p]=i;}22     for(int i=1;i<=n;i++)    23     {
   int p=read();24     b[i]=a[p];}25     for(int i=1;i<=n;i++)26     {27         int p=lower_bound(ans+1,ans+tot+1,b[i])-ans;28         ans[p]=b[i];29         if(p==tot+1)    tot++;30     }31     printf("%d",tot);32     return 0;33 }