1822 - 最长公共子序列(LCS)(2)
题目描述
给出 1 \sim n 的两个排列 P_1 和 P_2，求它们的最长公共子序列。
和最长公共子序列(LCS)(1)问题不同的是，本题的 n 在 5 \sim 100000 之间。
输入
第一行是一个数 n ；（n 是 5 \sim 100000 之间的整数）
接下来两行，每行为 n 个数，为自然数 1 \sim n 的一个排列（1 \sim n 的排列每行的数据都是 1 \sim n 之间的数，但顺序可能不同，比如 1 \sim 5 的排列可以是：1 2 3 4 5，也可以是 2 5 4 3 1）。
输出
一个整数，即最长公共子序列的长度。
样例
输入
5 3 2 1 4 5 1 2 3 4 5
输出
3
说明
数据范围
对于 50\% 的数据，n≤1000；
对于 100\% 的数据，n≤100000。
来源
动态规划
标签
