LCS & LIS 学习笔记

例题及讲解

LIS

最长上升子序列 (Longest Increasing Subsequence,LIS),一个数列中最长单调递增子序列

例如 1 2 5 8 8 2 9 的 LIS 为 1 2 5 8 9,长度为 5.

模板题:Hdu 1257

某国发展出一种导弹拦截系统,它的第一发炮弹能够到达任意的高度,以后每一发炮弹都不能超过前一发的高度,给你一个导弹依此飞来的高度序列,请帮助计算一下最少需要多少套拦截系统.

O(n^2) DP 解法

设 $ dp(i) $ 为前 $ i $ 个数以 $ i $ 结尾的 LIS 长度。

则 $ dp(i) = max(dp(j)+1|1 \leq j < i, a_j < a_i) $, $ a_i $ 为原数列。

初始化 $ dp(i) = 1 $,因为此时为一个数的最长上升子序列

代码(未编译):

1
2
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j) if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);

注意答案不是 $ dp(n) $,而是 $ max(dp(i)|1 \leq i \leq n) $

此做法时间复杂度为 $ O(n^2) $.

对于 Hdu 1257 的解法,我们只需要求出序列的最长上升子序列即可,因为有几个上升子序列就说明要开多少套拦截系统。最长上升子序列中必然不可能两个数用一个系统。

O(nlogn) 数据结构优化 DP 解法

例题:Hdu 1950

$ T $ 组数据询问,每个询问包含一个 $ n $ 长序列,求 LIS。 ( $ n \leq 40000 $ )

原状态不能快速求出 LIS,我们试着换状态。

设 $ dp(x) $ 为以 $ x $ 值结尾的 LIS 长度。

则每次顺序扫描,$ dp(a_i) = max(dp(x)|x < a_i) $, $ a_i $ 为原序列

然后,我们观察 $ max(dp(x)|x < a_i) $,发现这个可以开一个数据结构维护 $ a_i $ 的值域来 $ O(logn) $ 求解。

具体解法是,顺序扫描 $ a_i $ ,每次在数据结构中查询值域区间 $ [0, a_i) $ (有可能有的题目值域会出现负数,所有数加上一个大正数即可,适当调整左端点的值)的最大值 $ x $,然后直接转移 $ dp(a_i) = x + 1 $。之后再将数据结构中 $ a_i $ 的位置修改为 $ dp(a_i) $。

参考代码 (使用线段树维护区间最大值):

1
2
3
4
5
6
7
// 线段树维护区间最大值
int ans = 0;
for (int i = 1; i <= n; i++) {
dp[a[i]] = query(1, 0, MAXN, 0, a[i]) + 1;
ans = max(ans, dp[a[i]]); // 答案是所有的,不是一个 dp 值
update(1, 0, MAXN, a[i], dp[a[i]]);
}

此做法时间复杂度为 $ O(nlogn) $.

当然这个做法可以用树状数组来替换,代码会更简洁一些.

O(nlogn) 贪心二分做法

我们开一个数组 $ b $,当前长度为 $ len $。

然后我们顺序把 $a$ 数组(原序列)的数加入数组 $ b $

如果当前 $ a_i > b_{len}$,那么直接将 $ a_i $ 插入 $ b $, 即 $ b_{len + 1} = a_i$

否则在 $ b $ 中找到一个数比 $ a_i $ 刚刚大一点的数,然后将这个位置用 $ a_i $ 替换掉。

此时 $ len $ 是 LCS 的长度。

假如我们有 2 5 4 8 3 4 5 这个序列,那么我们操作是

2 加入 $ b $, 此时 $ b = 2 $
5 加入 $ b $, 此时 $ b = 2, 5 $
4 加入 $ b $, 此时 $ b = 2, 4 $
8 加入 $ b $, 此时 $ b = 2, 4, 8 $
3 加入 $ b $, 此时 $ b = 2, 3, 8 $
4 加入 $ b $, 此时 $ b = 2, 3, 4 $
5 加入 $ b $, 此时 $ b = 2, 3, 4, 5 $

此时 $ len = 4 $ 为 LIS 长度。 注意 $ b $ 不是 LIS,

为什么是对的呢?

其实每次操作的 $ len $ 相当于当前找到的 LIS。每次如果当前数 $ a_i $ 比 $ b $ 中所有数都大,那么这个 $ a_i $ 可以对当前答案产生 $ 1 $ 的贡献。反之,就可以将这个数替换掉 $ b $ 中的某个数,使得 $ b $ 中的数保持单调递增但是整体尽量最小,以便于后面的数加入产生贡献。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n, a[40005], b[40005], len;
void clean() {
ms(b, 0), len = 0;
}
int solve() {
scanf("%d", &n);
clean();
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
b[1] = a[1], len = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] > b[len]) b[++len] = a[i];
else {
int p = lower_bound(b + 1, b + 1 + len, a[i]) - b;
b[p] = a[i];
}
}
printf("%d\n", len);
return 0;
}

此做法时间复杂度为 $ O(nlogn) $.

LCS

最长公共子序列 (Longest Common Subsequence,LCS),即两个或两个以上数列中最长的公共子序列。

例如 1 2 5 8 8 2 9 和 1 3 5 8 9 9 9 的 LCS 为 1 5 8 9

模板题:Hdu 1159

求两个字符串的最长公共子串。

O(n^2) DP 解法

设 $ dp(i, j) $ 为第一个序列匹配到 $ i $,第二个序列匹配到 $ j $ 的 LCS 长度。

$ dp(i, j) = dp(i - 1, j - 1) + 1$,当且仅当 $ a_i=b_j $ (两个原序列)
$ dp(i, j) = max(dp(i - 1, j), dp(i, j - 1))$,当且仅当 $ a_i \ne b_j $

代码(未编译):

1
2
3
4
5
for (int i = 1; i <= lena; ++i)
for (int j = 1; j <= lenb; ++j) {
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

此做法时间复杂度为 $ O(n^2) $.

O(nlogn) 解法

在所有数不相同或者排列的情况下能够完成 LCS 转化为 LIS 从而 $ O(nlogn) $ 时间复杂度求解,见下面综合中的 LCS 转 LIS。

如果有相同数也可以做,但是非常麻烦。

求 LCS 的方案

例题:luogu 2516

对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。

第一问就是前面提到的 $ O(n^2) $的算法,主要看第二问

对于第二问,我们当前第一问的 DP 状态是 $ dp(i, j) $ 表示第一个串匹配到 $ i $,第二个串匹配到 $ j $ 的最长公共子序列。

然后我们再加一个数组 $ g(i, j) $ 表示第一个串匹配到 $ i $,第二个串匹配到 $ j $ 的最长公共子序列方案数。

对于这个数组的转移:

当 $ a_i = b_j $ 时,方案数加上$ g(i-1,j-1) $ 如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $,那么加上这些方案数,我们发现这个并不会重复

否则如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $,那么加上这些方案数。但是如果当前还等于 $ dp(i-1, j-1) $,说明 $ a_i , b_j $ 没做贡献,两个 LCS 均是从$i-1,j-1$的位置转移而来,减掉$ g(i-1,j-1) $即可。

注意开滚动数组,这种题目很容易就 MLE 爆 0 了

这种求方案数的方法很好,利用了一些容斥知识

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (int i = 0; i <= lb; ++i) g[cur ^ 1][i] = 1; //cur 表示滚动数组当前的位置,可以理解为 i。 cur ^ 1 为对称位置,可以理解为 i - 1。
for (int i = 1; i <= la; ++i) {
for (int j = 0; j <= lb; ++j) dp[cur][j] = 0, g[cur][j] = 0;
g[cur][0] = 1;
for (int j = 1; j <= lb; ++j) {
dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - 1]);
if (a[i] == b[j]) {
dp[cur][j] = dp[cur ^ 1][j - 1] + 1;
g[cur][j] = g[cur ^ 1][j - 1];
if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
} else {
if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
if (dp[cur][j] == dp[cur ^ 1][j - 1]) g[cur][j] = (g[cur][j] - g[cur ^ 1][j - 1] + MO) % MO;
}
}
}
cur ^= 1;
}
printf("%d\n%d\n", dp[cur ^ 1][lb], g[cur ^ 1][lb]);

综合

LIS 转 LCS

LIS 问题在数字不重复情况下可以转化为 LCS 问题来求解。

具体方法是把原数组 $ a $ 增序排序后得到 $ b $,然后 $ a, b $ 的 LCS 长度就是原序列 $ a $ 的 LIS 长度。

例如 1 2 5 8 2 9 排序后为 1 2 2 5 8 9,两个序列 LCS 为 1 2 5 8 9

因为 $ LIS $ 是单调递增的,而排序后的数组也是单调递增的,所以两个串的 LCS 就是 LIS。

将问题互化了一下,两个算法都可以 $ O(n^2) $ 完成。可能在有的题目中会用到。

LCS 转 LIS

考虑所有数不相同或者排列的情况下能够完成 LCS 转化为 LIS 。

例题:Luogu 1439

给出1-n的两个排列P1和P2,求它们的最长公共子序列

这里只有排列,说明了什么?我们可以找到第二个序列每个元素在第一个序列的位置,那么我们用一个 map 来进行映射处理 (也就是找到“第二个序列每个元素在第一个序列的位置”)

例如:

3 4 2 1 5 和 1 3 4 5 2,“第二个序列每个元素在第一个序列的位置”(“对应序列”)序列为 4 1 2 5 3

然后我们可以观察发现 4 1 2 5 3 的 LIS 即为 LCS。

这个结论是正确的。

我们可以想想,“第二个序列每个元素在第一个序列的位置”序列是按照第二个序列的顺序来排的,也就是说这个序列第一个数 4 表示的是第二个序列第一个数在第一个序列的位置,而不是第二个数的。然后我们知道在第一个序列中求得的 LCS 子序列从左到右序号一定是递增的,所以在按第二个序列数排的“对应序列”中找 LIS 就可以找出两个序列的 LCS。因为第二个序列求得的 LCS 子序列从左到右序号也一定是递增的。

就相当于固定了第二个序列中元素的顺序,然后根据第一个序列中元素顺序来求一个交。

代码:

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ma[a[i]] = i;//ma 为 map
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i) b[i] = ma[b[i]];
tax[1] = b[1], len = 1;
for (int i = 2; i <= n; ++i) {
if (b[i] > tax[len]) tax[++len] = b[i]; else {
int p = lower_bound(tax + 1, tax + 1 + len, b[i]) - tax;
tax[p] = b[i];
}
}
printf("%d\n", len);

对于有重复数的,我们也能做,但是代码非常复杂。。
假如有 1 2 3 1 4 和 2 3 1 1 4,我们将“第二个序列每个元素在第一个序列的位置”(“对应序列”)序列的元素修改为一个集合,即比如第二个序列 1 对应两个位置,为 $(1, 4)$,然后根据这个来得到“对应序列”(上面例子的“对应序列”:2 3 1 4 1 4 5),拆开集合的大括号继续做即可,注意可能有的数字对于空集的情况,代码太难写也没找到题就放这里读者有兴趣可以写写~

LCIS

顾名思义,LCIS 就是最长公共上升子序列。

例题:tyvj 1071

求两个序列的最长公共上升子序列。

我们可以设 $ dp(i, j) $ 为 $ a $ 序列匹配到 $ i $ 位置, $ b $ 序列匹配到 $ j $ 位置,以 $ b_j $ 结尾的 LCIS

参考代码:

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; ++i) {
int k = 0;
for (int j = 1; j <= n; ++j) {
if (a[i] == b[j]) f[j] = max(f[j], f[k]+1), ans = max(ans, f[j]); else {
if (b[j] < a[i] && f[j] > f[k]) k = j;
}
}
}

一些题目

------ 本文结束 ------