洛谷P1439 排列LCS问题

P1439 排列LCS问题

题目描述

给出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

/*
    看到10W的规模,大致可以断定此题应该用O(nlogn)的解法,朴素的LCS算法时间复杂度为O(n^2),明显不可行。
    首先简化一下问题,假设P1恰好为单调递增的1,2,3,...n,那么很显然答案就是P2的最长上升子序列的长度(想一想,为什么?)
    问题是P1并非单调递增的,但我们可以假定它就是1,2,3,...,n,将P1[1]映射到1,P1[2]映射到2,……然后再将P2作相同的变换即可,这样只要求P2的最长上升子序列了。
    最长上升子序列是有O(nlogn)算法的,大致过程如下:
    建立栈a,每读入一个元素x,若x比栈顶元素大则x进栈,否则在栈中二分找到第一个大于x的元素a[k],并用x替换它,做完以后栈的大小就是序列的最长上升子序列的长度。
*/
#include<iostream>
#include<cstdio>
#define maxn 100010
using namespace std;
int n,a[maxn],b[maxn],top,st[maxn];
int main(){
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        a[x]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        b[i]=a[x];
    }
    st[++top]=b[1];
    for(int i=2;i<=n;i++){
        if(b[i]>st[top])st[++top]=b[i];
        else {
            int l=1,r=top,pos;
            while(l<=r){
                int mid=(l+r)>>1;
                if(st[mid]>=b[i])pos=mid,r=mid-1;
                else l=mid+1;
            }
            st[pos]=b[i];
        }
    }
    printf("%d",top);
}
原文地址:https://www.cnblogs.com/thmyl/p/7494944.html