最长公共上升子序列 (LCIS, Longest Common Increasing Subsequence)：在给定两个序列中找到最长的公共子序列，满足子序列升序。

模板题：Acwing 272

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 $A$ 和 $B$，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 $A$ 和 $B$ 的长度均不超过 $3000$。

输入格式

第一行包含一个整数 $N$，表示数列 $A$，$B$ 的长度。

第二行包含 $N$ 个整数，表示数列 $A$。

第三行包含 $N$ 个整数，表示数列 $B$。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围

$1\le N\le 3000$,序列中的数字均不超过 $2^{31}-1$。

输入样例

4
2 2 1 3
2 1 2 3

输出样例

2

$O(n^3)$ 解法：三重循环 DP

思路

（本文默认下标从 $1$ 开始）

$dp(i,j):=$ 从 $A_1\sim A_i$ 选取若干数构成子序列，其中以 $B_j$ 为结尾（倒数第一位）的公共上升子序列的最大长度。

此时 $dp(i,j)$ 的集合可划分为如下几类：

• 子序列不含 $A_i$：$dp(i-1,j)$

• 子序列包含 $A_i$

  • 若 $A_i\ne B_j$：子序列不满足公共，忽略.

  • 若 $A_i=B_j$

    • 若公共上升子序列就是 $[B_j]$，因此长度为 $1$

    • 若公共上升子序列为 $[\cdots ,B_1,B_j]$

      • 如果 $B_1\ge B_j$：子序列不满足上升，忽略。
      • 如果 $B_1<B_j$：长度为 $dp(i-1,1)+1$.

    • 若公共上升子序列为 $[\cdots ,B_2,B_j]$

      • 如果 $B_2\ge B_j$：子序列不满足上升，忽略。
      • 如果 $B_2<B_j$：长度为 $dp(i-1,2)+1$.
    • $\cdots \cdots$

    • 若公共上升子序列为 $[\cdots ,B_{j-1},B_j]$

      • 如果 $B_2\ge B_j$：子序列不满足上升，忽略。
      • 如果 $B_2<B_j$：长度为 $dp(i-1,j-1)+1$.

将如上所有划分的结果求最大值，即可得到 $dp(i,j)$ 的值。

代码

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

void solve()
{
    int N;
    cin >> N;
    vector<int> A(N + 10), B(N + 10);
    vector<vector<int>> dp(N + 10, vector<int>(N + 10, 0));
    for (int i = 1; i <= N; i++)
        cin >> A[i];
    for (int i = 1; i <= N; i++)
        cin >> B[i];
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (A[i] == B[j])
                for (int k = 0; k < j; k++)
                    if (B[k] < B[j])
                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++)
        ans = max(dp[N][i], ans);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

$O(n^2)$ 解法：将 DP 进行简化

思路

观察上述朴素 DP 法，可以发现第三层循环算的是在 $0\le x\le j-1$ 范围内，$dp(i-1,x)+1$ 的最大值，而第二层循环做的是 $j$ 从 $1$ 到 $N$ 的遍历。由此可见第三层循环做了非常多次重复计算，我们不妨将上次计算的结果保存下来，用于递推本次的结果，即：

$$re{s}_j=max\{re{s}_{j-1},dp(i-1,j)+1\}$$

由此即可省去第三层循环，将 DP 等价变形从而实现简化。

代码

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(n^2)$

  • 可使用滚动数组将空间复杂度降低到 $O(n)$

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

void solve()
{
    int N;
    cin >> N;
    vector<int> A(N + 10), B(N + 10);
    vector<vector<int>> dp(N + 10, vector<int>(N + 10, 0));
    for (int i = 1; i <= N; i++)
        cin >> A[i];
    for (int i = 1; i <= N; i++)
        cin >> B[i];
    for (int i = 1; i <= N; i++)
    {
        int maxv = 1;
        for (int j = 1; j <= N; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (A[i] == B[j])
                dp[i][j] = max(dp[i][j], maxv);
            if (B[j] < A[i])
                maxv = max(maxv, dp[i - 1][j] + 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++)
        ans = max(dp[N][i], ans);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}