P1439 【模板】最长公共子序列

universehyf

题目描述

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

输入输出格式输入格式：

第一行是一个数n，

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

输出格式：

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

输入输出样例输入样例#1：

[size=1.2][url=]复制[/url]

5 3 2 1 4 51 2 3 4 5
输出样例#1：

[size=1.2][url=]复制[/url]

3

说明

【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

universehyf

感谢蒋巨佬的思路

1. #include<iostream>
   
2. #include<string>
   
3. using namespace std;
   
4. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
5. const int MAXN=100010;
   
6. int n,a[MAXN],b[MAXN],mp[MAXN],f[MAXN],ans,l,r,mid;
   
7. int main()
   
8. {
   
9.     cin>>n;FOR(i,1,n) cin>>a[i];FOR(i,1,n) cin>>b[i];
   
10.     FOR(i,1,n) mp[a[i]]=i;f[0]=0;
    
11.     FOR(i,1,n)
    
12.     {
    
13.         if(mp[b[i]]>f[ans]) f[++ans]=mp[b[i]];
    
14.         else{
    
15.             l=0;r=ans;
    
16.             while(l<r)
    
17.             {
    
18.                 mid=l+(r-l)/2;
    
19.                 if(mp[b[i]]>=f[mid]) l=mid+1;
    
20.                 else r=mid;
    
21.             }
    
22.         }f[l]=min(mp[b[i]],f[l]);
    
23.     }cout<<ans;
    
24.     return 0;
    
25. }

复制代码