← 返回题单

题单练习二分

← 上一题下一题 →

A70702 | $最长公共子序列(LCS)(1)$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给出 1 \sim n 的两个排列 P_1 和 P_2 ，求它们的最长公共子序列。

输入格式

第一行是一个数 n ；（ n 是 5 \sim 1000 之间的整数） 接下来两行，每行为 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++ 编辑器

输入

输出