A70703. 最长公共子序列(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）。
输出格式
一个整数，即最长公共子序列的长度。
输入输出样例
输入 #1
5 3 2 1 4 5 1 2 3 4 5
输出 #1
3
说明/提示
## 思路
用回溯生成排列：选一个未用数字 → 递归 → 撤销。
## 步骤
1. 读入 $n$ 或序列。
2. DFS/回溯枚举每个位置。
3. 按题面顺序输出所有排列。
用回溯生成排列：选一个未用数字 → 递归 → 撤销。
## 步骤
1. 读入 $n$ 或序列。
2. DFS/回溯枚举每个位置。
3. 按题面顺序输出所有排列。