首页 资讯 农业 汽车 房产 科技 养老 教育 展会 自媒体
智能 互联网 摄影 手机 VR

洛谷P1439 【模板】最长公共子序列

来源:互联网 作者:高晓娜 人气: 发布时间:2018-11-09


题目描述

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

嘤嘤嘤我看不懂题解啊


#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 3;
int n;
int a[N],b[N],f[N],v[N];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
v[a[i]] = i;
}
for(int i = 1;i <= n;i++)
{
scanf("%d",&b[i]);
f[i] = 0x7ffffff;
}
int len = 0;
for(int i = 1;i <= n;i++)
{
int l = 0,r = len,mid;
if(v[b[i]] > f[len])
{
f[++len] = v[b[i]];
}
else
{
while(l < r)
{
int mid = (l + r)/2;
if(f[mid] > v[b[i]])r = mid;
else l = mid + 1;
}
f[l] = min(v[b[i]],f[l]);
}
}
printf("%d",len);
return 0;
}

?




免责声明:本文仅代表作者个人观点,与华纳网无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
责任编辑:高晓娜
地址: 辽宁省大连市中山区港湾街20号名仕财富中心B座1517室 联系电话: 0411-84950851
© 2017 大连华纳文化传媒有限公司 All rights reserved
经营许可证编号:辽B2-20170212 备案号:辽ICP备17007383号-2
辽公网安备 21021102000241