利用图论解决子序列问题

分类: 文章 • 2025-02-24 22:00:06

利用图论解决公共子序列问题子序列

解析：

以第一个字符串为基准，由于是1-n的排列，每个数字都不同，每个数字设为 $[u]$ 都遍历之后的数字设为 $[v]$ 尝试连边，连边的规则应该符合子序列规则：在每个字符串中 $u$ 出现的位置都在 $v$ 的前面。最后跑一次最长路即可，必须实现记忆化搜索，否则超时。