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