全排列的最长公共子序列

最长公共子序列

#include<iostream>
#define maxn 100010
using namespace std;

int A[maxn],B[maxn],C[maxn],f[maxn],f1[2333][2333];
int main(){
    将A序列一一映射成1,2,3...n,便等价于求B序列的最长上升子序列长度.
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>A[i];
    for(int i=1;i<=n;i++)cin>>B[i];
    O(n^2)求一般情况
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(A[i]==B[j])f1[i][j]=f1[i-1][j-1]+1;
    else f1[i][j]=max(f1[i-1][j],f1[i][j-1]);
    cout<<f1[n][n];cout<<endl;
    O(nlogn)求排列情况
    for(int i=1;i<=n;i++)C[A[i]]=i;
    for(int i=1;i<=n;i++)B[i]=C[B[i]];
    f[1]=B[1];int lon=1;
    for(int i=2;i<=n;i++){
        if(B[i]>f[lon])f[++lon]=B[i];
        else{
            int l=1,r=lon;
            while(l<r){
                int mid=(l+r)>>1;
                if(f[mid]<B[i])l=mid+1;
                else r=mid;
            }
            f[l]=B[i];
        }
    }
    cout<<lon;
    return 0;
}