1821 - 最长公共子序列(LCS)(1)

题目描述

给出 1 \sim n 的两个排列 P_1P_2 ,求它们的最长公共子序列。

输入

第一行是一个数 n ;( n5 \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 )。

输出

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

样例

输入

5 
3 2 1 4 5
1 2 3 4 5

输出

3
来源

动态规划

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 2626
通过人数 1722
金币数量 2 枚
难度 基础


上一题 下一题