Toggle navigation
码蜂编程
常见问答
问题
来源/分类
状态
排名
竞赛&作业
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
问题1822--【提高】最长公共子序列(LCS)(2)
1822: 【提高】最长公共子序列(LCS)(2)
[命题人 :
]
时间限制 :
1.000
sec
内存限制 :
128 MB
提交
解决: 1
提交量: 1
统计
题目描述
给出1-n的两个排列P1和P2,求它们的最长公共子序列。
和最长公共子序列(LCS)(1)问题不同的是,本题的n在5-100000之间。
输入
第一行是一个数n;(n是5-100000之间的整数)
接下来两行,每行为n个数,为自然数1-n的一个排列(1-n的排列每行的数据都是1-n之间的数,但顺序可能不同,比如1-5的排列可以是:1 2 3 4 5,也可以是2 5 4 3 1)。
输出
一个整数,即最长公共子序列的长度。
样例输入
Copy
5 3 2 1 4 5 1 2 3 4 5
样例输出
Copy
3
提示
对于50%的数据,n≤1000
对于100%的数据,n≤100000
来源/分类
动态规划