【模板】最长公共子序列
程序员文章站
2024-01-14 15:54:52
...
题目
https://www.luogu.org/problemnew/solution/P1439
思路
用一个类似hash的思想,使得f[a[i]]=i
可以发现,如果序列和a相同,则序列满足递增。
so,求一个lis就行啦
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int a1[100010],a2[100010];
int belong[100010];
int f[100010],b[100010],len;
int main()
{
freopen("a.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a1[i]);
belong[a1[i]]=i;
}
for(int i=1;i<=n;i++)
scanf("%d",&a2[i]);
for(int i=1;i<=n;i++)
{
if(belong[a2[i]]>b[len])
{
b[++len]=belong[a2[i]];
f[i]=len;
continue;
}
int k=lower_bound(b+1,b+len+1,belong[a2[i]])-b;
b[k]=belong[a2[i]];
f[i]=k;
}
printf("%d\n",len);
return 0;
}