子序列有关问题总结

我们定义子序列为：从原序列中选取若干个元素，按原序列的顺序排列的序列。

1. 最长上升子序列问题

给定一个长为\(n\)的序列\(a\)，求其中的最长的上升子序列的大小。

1.1 动态规划做法

设\(dp_i\)为以\(a_i\)结尾的最长的上升子序列的大小，则序列\(a\)上最长的上升子序列的大小为\(\mathop{\max}_{1\le i\le n}dp_i\)。

对于每个\(dp_i\)，如果存在\(j < i\)且\(a_j<a_i\)，说明可以把\(a_i\)接到\(a_j\)后面形成一个上升序列。此时以\(a_i\)结尾的序列的大小为\(dp_j+1\)，所以我们遍历\(j\in [1,i-1]\)，有转态转移方程\(dp_i=\mathop{\max}_{1\le j< i,a_j<a_i}dp_j+1\)，从而求出\(dp_i\)的最大值。

这个算法的复杂度为\(O(n^2)\)。

模板题代码：

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> dp(n, 1);
    int ans = 0;
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[j] < a[i]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << "\n";

    return 0;
}

1.2 贪心+二分做法

设\(f_{len}\)为长度为\(len\)的上升子序列的末尾元素。每当有新元素添加到\(f\)末尾之后，\(len\)的最大长度加1，说明当前上升子序列的最大长度加1。所以，最后的答案就为\(len\)的最大长度。

从前往后遍历序列\(a\)的所有元素，如果\(a_i\)的大于\(f\)的末尾元素，就把\(a_i\)加到\(f\)的末尾。

要想获得最长的\(len\)，就要尽量使\(f\)中每位置的元素尽量小，这样之后才有可能有更多的元素添加到\(f\)的末尾。并且容易证明\(f\)是单调的，所以，当\(a_i\)小于等于\(f\)的末尾元素时，就二分找到\(f\)中第一个大于等于\(a_i\)的元素，并用\(a_i\)替换这个元素。

这个做法的复杂度为\(O(n\log n)\)。

模板题代码：

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> f{0};// f的初始值根据题目给出的数据大小决定
    for(int i = 0; i < n; i++) {
        if(a[i] > f.back()) {
            f.push_back(a[i]);
        } else {
            int p = upper_bound(f.begin(), f.end(), a[i]) - f.begin();
            f[p] = a[i];
        }
    }

    cout << f.size() - 1 << "\n";

    return 0;
}

1.3 树状数组优化dp

现在回过头再看之前动态规划的做法，注意到对于每个\(dp_i\)，要找到\(j\in[1,i-1],dp_j\)的最大值，既然是区间最大值问题，那么我们就可以用树状数组进行优化。

设\(fen_i\)保存指定区间的最大值。我们从前往后遍历所有\(a_i\)，每次询问\(fen_{a_i-1}\)以及之前节点的最大值，得到的数值加1即为以\(a_i\)结尾的子序列的最大值\(res\)。更新维护答案后，再把\(fen_{a_i}\)的值设为\(res\)。

有几个需要注意的地方，树状数组的大小由原序列数据的范围决定，当范围太大时记得离散化一下。本题是求最大上升子序列，要求严格递增，所以要询问\(fen_{a_i-1}\)以及之前的节点。如果是求非下降子序列，就询问\(fen_{a_i}\)以及之前的节点。

这个做法的复杂度为\(O(n\log n)\)

模板题代码：

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int N = 1e6 + 10;
array<int, N> fen;

void update(int x, int k) {
    for(int i = x; i < N; i += i & -i) {
        fen[i] = max(fen[i], k);
    }
}

int query(int x) {
    int res = 0;
    for(int i = x; i > 0; i -= i & -i) {
        res = max(res, fen[i]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    for(int i = 0; i < n; i++) {
        int res = query(a[i] - 1) + 1;
        ans = max(ans, res);
        update(a[i], res);
    }

    cout << ans << "\n";

    return 0;
}

1.4 其它最长子序列问题

除了最长上升子序列问题外，还有最长不下降子序列，最长下降子序列，最长不下降子序列。

若是第一种dp做法，更改一下条件即可。若是第二种二分做法，除了更改条件，还要注意是使用upper_bound还是lower_bound。

若是第三种树状数组优化dp的做法，当求下降或不上升子序列时，从后往前遍历原序列\(a\)，否则从前往后遍历。当上升或下降子序列时，为了避免访问重复的元素取得错误的结果，每次询问的应该是\(fen_{i-1}\)以及之前的节点。

1.5 最长子序列问题的扩展

• 对于dp做法，我们最后可以的到一个答案数组\(dp_i\)，表示记录以\(i\)结尾的最长子序列。现给定一个定理：如果有\(i<j\)且\(dp_i\ge dp_j\)，那么\(a_i\)和\(a_j\)一定不能形成一个符合条件的子序列。考虑反证法，如果\(a_i\)和\(a_j\)能形成一个符合条件的子序列，根据转态转态方程可知，\(dp_j\)至少比\(dp_i\)大1，矛盾。

  如果把一个序列的所有顺序对或逆序对之间连边，建图。那么根据上面的定理，我们按条件求最长子序列，得到的dp数组值相同的节点一定不相邻。

• 上面的定理反过来是不一定成立的，即：如果有\(i<j\)且\(dp_i<dp_j\)，那么\(a_i\)和\(a_j\)不一定能形成一个符合条件的子序列。因为\(dp_i\)和\(dp_j\)并不能确定\(a_i\)和\(a_j\)的大小关系。假设我们求[10,11,1,2,3]的最长上升子序列，\(dp_2\)和\(dp_5\)分别为2和3，但是11和3不能形成上升子序列。

• Dilworth定理：对偏序集\(<A,\le>\)，设\(A\)中的最长链的长度为\(n\)，那么将\(A\)中的元素分成不相交的反链，反链的个数至少是\(n\)。这个定理可以简述为：一个序列中最少不上升子序列的个数为最长上升子序列的长度。这个定理对其它最长子序列问题也适用。

2. 最长公共子序列问题

给定两个长分别为\(n,m\)的排列\(a,b\)，求\(a,b\)的最长公共子序列。

2.1 最长公共子序列的大小

设\(dp_{i,j}\)为考虑\(a\)的前\(i\)个元素，\(b\)的前\(j\)个元素的最长公共个子序列的大小，则最终的答案为\(dp_{n,m}\)。

遍历\(a\)和\(b\)，如果有\(a_i=b_j\)，说明当前求得的最长公共子序列的大小加1，则\(dp_{i,j}=dp_{i-1,j-1}+1\)。否则，当前的最长公共子序列的大小一定是\(dp_{i-1,j}\)或\(dp_{i,j-1}\)的其中一个，则有\(dp_{i,j}=\mathop \max(dp_{i-1,j},dp_{i,j-1})\)。

这个做法的复杂度为\(O(nm)\)。

模板题代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    while(cin >> a >> b) {
        int n = a.size(), m = b.size();
        vector dp(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        cout << dp[n][m] << "\n";
    }

    return 0;
}

2.2 求最长公共子序列

如图，假设\(a\)为"ABCDEDC"，\(b\)为"EADEDAC"，下图每个单元\((i,j)\)即为上面的做法中求得的\(dp_{i,j}\)。

我们先从矩阵的右下角开始，如果有\(a_i=b_j\)，就把对应的元素加入到答案中，并往左上角移动。否则的话，它的左边和上边就一定有一个数与它相等，就往与它相等的数的方向移动一格。如此移动直到移动到左上角为止。这其实就是把上面动态规划的做法倒过来而已。

这样我们就获得了最长公共子序列了，下图就显示了它的移动路径，并标出了加入到答案的元素。

这个做法的复杂度为\(O(n+m)\)。

2.3 公共子序列问题的扩展

• 假设要求的序列增加到三个，求最长公共子序列的大小还是用dp的做法。设\(dp_{i,j,k}\)为分别考虑三个序列的前\(i\)，前\(j\)，前\(k\)个元素的最长公共子序列。那么根据两个序列时的做法，有状态转移方程\(dp_{i,j,k}= \begin{cases} dp_{i-1,j-1,k-1}+1 & A_i=B_j=C_k \\ \mathop\max(dp_{i-1,j,k},dp_{i,j-1,k},dp_{1,j,k-1}) & else \\ \end{cases}\)

  此外，求最长公共子序列也是类似的。如果三个位置的元素相等，则加入到答案中，否则移动到相等的数的位置。

• 如果给出的两个序列中，每个序列的中的元素都没有重复，那么它可以看成求最长上升子序列问题。

  假设序列\(a\)为[3,2,1,4,5]，序列\(b\)为[1,2,3,4,5]。给两个序列重新标号， 把3变成A，2变成B……于是最终两个序列变成\(a\)为[A,B,C,D,E]，\(b\)为[C,B,A,D,E]。这样标号后，最长公共子序列的长度不会变，但是\(a\)变成了递增的，那么两个序列的公共子序列也是递增的。所以，\(b\)的最长上升子序列的大小，就是最长公共子序列的大小。

  注意：如果\(b\)中的有元素在\(a\)中没有出现，那么它对答案没有贡献，直接忽略即可。