题目描述
给出$1$-$n$的两个排列$P_1$和$P_2$，求它们的最长公共子序列。
输入格式
第一行是一个数$n$
接下来两行，每行为$n$个数，为自然数$1$-$n$的一个排列。
输出格式
一个数，即最长公共子序列的长度
找出两个序列共同出现的元素，每个元素包括两个维度，一个为在$a$中的位置，一个为在$b$中的位置，我们首先保证一个序列在$a$中的位置单调递增，那么只要这个序列在$b$中得位置也单调递增，他们就是最长公共子序列。
代码如下：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 int n,num; 6 int s1[1000005],s2[100005],c[100005]; 7 struct node 8 { 9 int x,y; 10 }; 11 node a[1000005]; 12 inline int read() 13 { 14 int x = 1,a = 0; 15 char ch = getchar(); 16 while(ch < '0' || ch > '9'){ 17 if(ch == '-')x = -1; 18 ch = getchar(); 19 } 20 while(ch <= '9'&&ch >= '0'){ 21 a = a * 10 + ch - '0'; 22 ch = getchar(); 23 } 24 return x*a; 25 } 26 bool cmp(node x,node y) 27 { 28 return x.x<y.x; 29 } 30 int main() 31 { 32 // freopen("1.in","r",stdin); 33 // freopen("1.out","w",stdout); 34 n=read(); 35 for (int i = 1;i <= n ;i++) 36 { 37 s1[i]=read(); 38 a[s1[i]].x=i; 39 } 40 for (int i = 1;i <= n;i++) 41 { 42 s2[i]=read(); 43 a[s2[i]].y=i; 44 } 45 sort(a+1,a+n+1,cmp); 46 for (int i = 1;i <= n;i++) 47 { 48 if (c[num]<a[i].y) 49 c[++num]=a[i].y; 50 else 51 { 52 int pos=lower_bound(c+1,c+num+1,a[i].y)-c; 53 c[pos]=a[i].y; 54 } 55 } 56 printf ("%d",num); 57 return 0; 58 }