P1439 【模板】最长公共子序列

P1439 【模板】最长公共子序列

题目描述

给出两个长度为 \( n \) 的排列 \( P_1 \) 和 \( P_2 \)，求它们的最长公共子序列（LCS）长度。

输入格式

• 第一行为整数 \( n \)
• 接下来两行，每行 \( n \) 个整数，表示排列 \( P_1 \) 和 \( P_2 \)

输出格式

一个整数，表示最长公共子序列的长度

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

3

算法思路

问题转换

利用排列的特性（元素唯一且覆盖 1~n），将LCS问题转换为最长递增子序列（LIS）问题：

1. 记录 \( P_1 \) 中每个元素的位置：pos[P1[i]] = i
2. 将 \( P_2 \) 转换为位置序列：s = [pos[x] for x in P2]
3. 求序列 \( s \) 的 LIS 长度即为原问题的 LCS 长度

复杂度优化

• 时间复杂度：\( O(n \log n) \)
• 空间复杂度：\( O(n) \)

代码实现

import bisect

n = int(input())
p1 = list(map(int, input().split()))
p2 = list(map(int, input().split()))

# 构建位置映射表
pos = [0] * (n + 1)
for i in range(n):
    pos[p1[i]] = i

# 将p2转换为位置序列
s = [pos[x] for x in p2]

# 贪心法求LIS
dp = []
for num in s:
    idx = bisect.bisect_left(dp, num)
    if idx == len(dp):
        dp.append(num)
    else:
        dp[idx] = num

print(len(dp))

代码解释

1. 输入处理：读取排列长度和两个排列
2. 位置映射：通过数组 pos 记录每个元素在 p1 中的下标
3. 序列转换：将 p2 转换为基于 p1 位置的序列 s
4. LIS求解：维护动态数组 dp，通过二分查找更新最小末尾值

正确性验证

以样例输入为例：

p1 = [3, 2, 1, 4, 5]
pos映射表为：
pos[3] = 0, pos[2] = 1, pos[1] = 2, pos[4] = 3, pos[5] = 4

p2 = [1, 2, 3, 4, 5]
转换为位置序列 s = [2, 1, 0, 3, 4]

求LIS：
序列 2 → 1 → 0 → 3 → 4 的最长递增子序列为 [0,3,4]，长度为3