概览

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

题解

• 集合表示f[i, j]： 所有由第一个序列的前i个字母，第二个序列的前j个字母, 且以b[j]结尾的构成的公共子序列，Max
  > 注意这里要加条件
• 状态计算：
  1. 所有包含a[i]的公共上升子序列 a[i]==b[j]
     > 按照倒数第2类划分， 序列倒数第1个数时null, b[1], b[2], .., b[j-1]
     > 进行枚举 f[i,k] + 1 因为b[j]大于，所以实际上就是
  2. 所有不包含a[i]的公共上升子序列 f[i-1, j]

代码

O(n^3)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++) {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) {
                f[i][j] = max(f[i][j], 1);
                for (int k = 1; k < j; k ++)
                   if (b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k] + 1);
            } // else 只剩下一种
        }

    int res = 1;
    for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}

代码的优化实际上就是对代码做等价变形

O(n^2)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);

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

    int res = 1;
    for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}