← 返回题目

题库练习最长公共子序列(LCS)(2)

← 上一题下一题 →

A70703 | $最长公共子序列(LCS)(2)$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输出格式

一个整数，即最长公共子序列的长度。

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

C++ 编辑器

输入

输出