题目描述

已知两个长度为n的序列a和b，求其最长公共上升子序列的长度。

公共上升子序列即满足以下条件的子序列：

1. 该序列是a和b的公共序列
2. 该序列是上升序列

状态定义

f[i][j]: a[1 - i], b[1 - j]且以b[j]结尾的最长公共上升子序列的长度。

这里的状态定义可以理解为结合了最长公共子序列与 最长上升子序列 。

• a[1 - i], b[1 - j]负责公共子序列
• 以b[j]结尾负责上升

状态转移

首先按照最长公共子序列问题考虑，可以分成两种情况：

• a[i] != b[j]: 此时包含不包含a[i]都是一样的，所以f[i][j]可以从f[i - 1][j]转移过来；
• a[i] = b[j]:此时一定需要包含a[i], f[i][j]可以从f[i - 1][q]($q \in [1, j-1]$)中满足a[i] = b[j] > b[q]中最大的一个转移过来

由上我们可以写出如下算法$O(n^3)$：

for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            // 不包括a[i]
            f[i][j] = f[i - 1][j]; 
            // 包括a[i]
            if(a[i] == b[j]) 
            {
                int maxv = 1;

                for(int q = 1; q < j; ++q)
                {
                    if(a[i] > b[q])maxv = max(maxv, f[i - 1][q] + 1); 
                }

                f[i][j] = max(f[i][j], maxv);
            }
        }
    }

观察发现, 下面这段循环是可以被优化掉的

for(int q = 1; q < j; ++q)
{
    if(a[i] > b[q])maxv = max(maxv, f[i - 1][q] + 1); 
}

原算法优化如下$O(n^2)$:

仔细理解maxv的含义

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;

int n, a[N], b[N], f[N][N]; // f[i][j] 表示a[1 - i]b[1 - j]，且以b[j]结尾的最长公共上升子序列长度

int main()
{
    cin >> n;
    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; 
        // maxv表示 a[1 - i]b[1 - j-1]
        // 以b[1] - b[j - 1]中的一个值b[q]结尾
        // 且满足 a[i] > b[q] 的最长公共上升子序列的长度
        for(int j = 1; j <= n; ++j)
        {
            // 不包括a[i]
            f[i][j] = f[i - 1][j]; 
            // 包括a[i]
            if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if(a[i] > b[j])maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for(int i = 1; i <= n; ++i)res = max(res, f[n][i]);
    cout << res << endl;
    return 0;
}