一个数, 即最长公共子序列的长度
找出两个序列共同出现的元素, 每个元素包括两个维度, 一个为在 a 中的位置, 一个为在 b 中的位置, 我们首先保证一个序列在 a 中的位置单调递增, 那么只要这个序列在 b 中得位置也单调递增, 他们就是最长公共子序列.
代码如下:
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int n,num;
- int s1[1000005],s2[100005],c[100005];
- struct node
- {
- int x,y;
- };
- node a[1000005];
- inline int read()
- {
- int x = 1,a = 0;
- char ch = getchar();
- while(ch <'0' || ch> '9'){
- if(ch == '-')x = -1;
- ch = getchar();
- }
- while(ch <= '9'&&ch>= '0'){
- a = a * 10 + ch - '0';
- ch = getchar();
- }
- return x*a;
- }
- bool cmp(node x,node y)
- {
- return x.x<y.x;
- }
- int main()
- {
- // freopen("1.in","r",stdin);
- // freopen("1.out","w",stdout);
- n=read();
- for (int i = 1;i <= n ;i++)
- {
- s1[i]=read();
- a[s1[i]].x=i;
- }
- for (int i = 1;i <= n;i++)
- {
- s2[i]=read();
- a[s2[i]].y=i;
- }
- sort(a+1,a+n+1,cmp);
- for (int i = 1;i <= n;i++)
- {
- if (c[num]<a[i].y)
- c[++num]=a[i].y;
- else
- {
- int pos=lower_bound(c+1,c+num+1,a[i].y)-c;
- c[pos]=a[i].y;
- }
- }
- printf ("%d",num);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3400570.html