【模板】最长公共子序列

//洛谷P1436 （模板）

我们定义映射f(ai)=i，那么两个排列可以转换为(f(a1),f(a2),...,f(an))=(1,2,...,n)和(f(b1),f(b2),...,f(bn))，我们进行这样的转换之后，就把本题转换为求最长上升子序列的长度的题目了。

最长上升子序列存在O(N log N)时间复杂度的算法，概述如下：

考虑两个数a[x]和a[y]，若x<y且g[x]==g[y]，那么在转移的过程中，选择a[x]更有潜力（证明是显而易见的，可以自己设计几组数据加深理解），可以获得最优的值，所以当g数组的值一样时，应选择最小的数。

按照g[i]==k分类，记录g[i]==k的所有i的最小值，g有两个特点：

1)f[i]在计算过程中单调不升

2)f数组是有序的，g[i]<=g[i+1]

根据这些性质，可以方便地求解：

1)设当前求出的LIS（最长上升子序列的简称，以后同此）长度为ans（初始值为1），当前元素为a[x]

2)如果a[x]>g[ans]，直接加入f数组的末尾，且ans++；否则在f数组中二分查找，找到第一个比a[x]小的数字g[k]（使用二分查找实现），g[k+1]=a[x]，这样做保证a[x]<=g[k+1]（根据性质1，2）

3)最后的ans即为答案

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,a[maxn],f[maxn],g[maxn],ans=1,cur; 
inline int bs(int k,int l,int r){   
    while(l<r){
        int mid=(l+r)>>1;
        if(k>=g[mid])l=mid+1;
        else r=mid;
    }
    return l;
}
//二分查找 bs(k,l,r)表示在[l,r]中寻找比k大的最小的数 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a),f[a[0]]=i;     //建立映射关系
    for(int i=0;i<n;i++) scanf("%d",a+i),a[i]=f[a[i]];//输入并同时处理映射
    g[1]=a[0];   //dp初始化 
    for(int i=1;i<n;i++){
        if(g[ans]<a[i])cur=++ans;
        else cur=bs(a[i],1,ans+1);
        g[cur]=a[i];
    }//dp处理，并记录ans 
    printf("%d",ans);
    return 0;
}