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

前置知识

最长上升子序列（及其二分求法）；
最长公共子序列（LCS）：两个序列中共同包含的最长子序列（可能有多个）；
二分。

暴力求 LCS

可用

dp_{i,j}

表示第一个序列的前

i

位，第二个串的前

j

位的 LCS 的长度。显然有状态转移方程：

\max(dp_{i,j}, dp_{i−1,j−1}+1) & \text{if }P_i=P_j,\\ \max(dp_{i−1,j}, dp_{i,j−1}) & \text{otherwise}. \end{matrix}\right.$$ 解释：如果当前的 $P_i=P_j$，那么有新的公共元素。我们可以选择新开一个子序列，或依附之前的子序列。\ 如果二者不相同，就只能继承前一个元素的 LCS 长度。 由于我们要把两个序列的每一对 $(i,j)$ 都枚举一遍，所以时间复杂度为 $\Theta(n^2)$。 但是，这个算法不能通过这一题。（不过[这题](https://www.luogu.com.cn/problem/P2758)是可以的，只要稍作“魔改”就可以了。） ### （特殊）优化 #### LCS 转化为 LIS 因为本题中保证 $P_1,P_2$ 分别为 $1,2,\dots,n$ 的两个排列，所以，$P_1$ 中的每个元素都可以在 $P_2$ 中找到。 而公共子序列只要保证在两序列中的顺序一样。 所以，我们可以用一个映射数组（记为 $m$）把 $P_2$ 中的数按 $P_1$ 中的顺序进行编号。\ 然后问题就被转化成了求 $m$ 的 LIS 长度，求出它即可。 时间复杂度即为求 LIS 的复杂度。如用二分求，为 $\Theta(n\log n)$，可过。 #### 二分求 LIS 本部分将简要介绍 LIS 的 $\Theta(n\log n)$ 求法。\ 如已学过，请忽略。 令 $g_i$ 表示在该序列中，**长度为 $i$ 的 LIS 的末尾数的最小值**。显然，$g_1=a_1$，且 $g$ 数组有一个重要性质：单调不减。 而之后的 $g_2,g_3,\dots,g_n$ 就等于 $g$ 数组中对应的 LIS 长度小于它且对应的 $g$ 值大于等于当前位置的数的第一个位置。由于 $g$ 数组有单调性，所以这个位置可以二分到。 即 $g_i = g_{i'}$，其中 $i'$ 表示符合上述条件的下标。 #### 实现 （只给出输入和算法实现，不可直接编译） ```cpp struct N { int data, id; }; N a[MAXN], b[MAXN]; int m[MAXN], g[MAXN], n, ans = 0; int main() { cin >> n; for(int i=1; i<=n; ++i){ cin >> a[i].data; m[a[i].data] = i; a[i].id = i; } for(int i=1; i<=n; ++i){ cin >> b[i].data; b[i].id = i; } memset(g, 0x77, sizeof g); g[1] = a[1]; for(int i=1; i<=n; ++i){ int x = m[b[i].data]; int pos = lower_bound(g+1, g+n+1, x) − g; ans = max(ans, pos); g[pos] = min(x, g[pos]); } cout << ans; return 0; } ``` ### 最后 假如 DP 欺骗了你，不要悲伤，不要心急。\ 忧郁的日子里需要学习；相信吧，胜利终将属于你。

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

文章操作

前置知识

暴力求 LCS

相关推荐

评论

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