P1439 排列LCS问题

- 56通过
- 220提交
题目提供者yeszy
标签二分动态规划
难度普及+/提高

提交该题讨论题解记录

题目描述

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

输入输出格式

输入格式：

第一行是一个数n，

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据规模】

对于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替换它，做完以后栈的大小就是序列的最长上升子序列的长度。

AC代码：

（头文件自动忽略就好）

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<string>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

using namespace std;

#define ll long long

#define N 100010

#define inf 1100000000

#define linf 999999999999999LL

#define xx first

#define yy second

typedef pair<int,int> diy;

inline const int read(){

    register int x=,f=;

    register char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m,len;

int a[N],b[N];

int main(){

    n=read();

    for(int i=;i<=n;i++) a[read()]=i;

    for(int i=;i<=n;i++) b[i]=a[read()];

    memset(a,,sizeof a);

    a[len=]=b[];

    for(int i=;i<=n;i++){

        if(b[i]>a[len])

            a[++len]=b[i];

        else

            a[lower_bound(a+,a+len+,b[i])-a]=b[i];

    }

    printf("%d\n",len);

    return ;

}

巴特西

P1439 排列LCS问题

P1439 排列LCS问题

最新讨论

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章