洛谷1439 排列LCS问题

本题地址：http://www.luogu.org/problem/show?pid=1439

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

3 2 1 4 5

1 2 3 4 5

输出样例#1：

说明

【数据规模】
对于50%的数据，n≤1000
对于100%的数据，n≤100000

【思路】

LCS转LIS + 二分优化LIS

首先明确题目的特殊性：序列为1-n的一个排列即一个序列中不存在重复的元素。

如果LCS正常思路算时间为O(n^2)而且空间需要二维，显然不适用于本题。

这里将第一个序列a重新编号为1..n，并以这个编号规则重新定义第二个序列b，则问题转化为求新的第二个序列的LIS。

O(nlogn)求LIS的方法：二分查找。构造一个g数组，g[i]表示d值为i且最小的a值，每次转移求d[i]可以从g中二分查找满足小于a[i]的最大d值，算法在白书上有过探讨(P62)这里不再赘述。

数据很大，可以考虑优化读入。

【代码】

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn = +;

 const int INF=<<;

 int n;

 int a[maxn],b[maxn],d[maxn];

 inline int read_int() {

     char c; c=getchar();

     while(!isdigit(c)) c=getchar();

     int x=;

     while(isdigit(c)) {

         x=x*+c-'';

         c=getchar();

     }

     return x;

 }

 int main() {

     n=read_int();

     int tmp[maxn];

     for(int i=;i<=n;i++) a[i]=read_int() , tmp[a[i]]=i;

     for(int i=;i<=n;i++) b[i]=read_int() , b[i]=tmp[b[i]];

     int g[maxn],ans=;

     for(int i=;i<=n;i++) g[i]=INF;

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

         int k=lower_bound(g+,g+n+,b[i])-g;

         d[i]=k;

         g[d[i]]=b[i];

         ans=max(ans,d[i]);  //return max

     }

     cout<<ans<<"\n";

     return ;

 }

巴特西

洛谷1439 排列LCS问题

最新文章

热门文章