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

· · 题解

前置知识

暴力求 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)。

但是，这个算法不能通过这一题。（不过这题是可以的，只要稍作“魔改”就可以了。）

（特殊）优化

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' 表示符合上述条件的下标。

实现

（只给出输入和算法实现，不可直接编译）

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 欺骗了你，不要悲伤，不要心急。\ 忧郁的日子里需要学习；相信吧，胜利终将属于你。