python/TangDou/AcWing/LIS/272_1.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;
// 通过了 10/13个数据
// O(n^3)
int main() {
    int n;
    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++)
        for (int j = 1; j <= n; j++) {
            // ① 二维DP打表的一般套路，都是可以直接从上一行继承的
            // ② 从题意出发，就是a中前i个数字，b中前j个数字，且以b[j]结尾的子序列中长度最大的
            // 那么，a中多整出一个数字来，最起码也是f[i-1][j]的值，不能更小
            f[i][j] = f[i - 1][j];
            // ③ 如果恰好 a[i]==b[j],那么就可以发生转移
            if (a[i] == b[j]) {
                int mx = 1; // 最起码a[i]==b[j]，有一个数字是一样嘀~
                // f[i-1]是肯定的了，问题是b的前驱在哪里？需要枚举1~j-1
                for (int k = 1; k < j; k++)
                    if (a[i] > b[k]) // j可以接在k后面，那么可能的最大值为f[i-1][k]+1
                        mx = max(mx, f[i - 1][k] + 1);
                // 更新答案
                f[i][j] = max(f[i][j], mx);
            }
        }
    int res = 0;
    // a数组肯定是火力全开到n就行，b数组中的位置就需要枚举了
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}