鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

洛谷P1439 最长公共子序列(LCS问题)

来源:互联网 作者:佚名 时间:2018-02-27 09:51
题目描述 给出1-n的两个排列P1和P2,求它们的最长公共子序列。 输入输出格式 输入格式: 第一行是一个数n, 接下来两行,每行为n个数,为自然数1-n的一个排列。 输出格式: 一个数,即最长公共子序列的长度 输入输出样例 输入样例#1:复制 5 3 2 1 4 51 2 3

题目描述

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

 

首先把第一个序列里面的数在第二个序列里面对应hash一下

然后就转化成了求最长上升子序列的问题

对于这种问题,可以用二分查找处理

每次找出大于等于他的第一个位置

替换即可

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN=100001;
 6 inline int read()
 7 {
 8     char c=getchar();int x=0,f=1;
 9     while(c<'0'||c>'9')    {if(c=='-')f=-1;c=getchar();}
10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
11 }
12 int a[MAXN];
13 int b[MAXN];
14 int ans[MAXN],tot=0;
15 int main()
16 {
17     int n;
18     scanf("%d",&n);
19     for(int i=1;i<=n;i++)    
20     {int p=read();
21     a[p]=i;}
22     for(int i=1;i<=n;i++)    
23     {int p=read();
24     b[i]=a[p];}
25     for(int i=1;i<=n;i++)
26     {
27         int p=lower_bound(ans+1,ans+tot+1,b[i])-ans;
28         ans[p]=b[i];
29         if(p==tot+1)    tot++;
30     }
31     printf("%d",tot);
32     return 0;
33 }

 

网友评论
<