LCS——经典的 DP 问题，给定两个长度为 $n$ 的排列，试问二者的最长公共子序列。这是经典的区间 DP 问题，

首先考虑朴素做法，定义 $dp[i][j]$ 来表示第一个串的前 $i$ 位，第二个串的前 $j$ 的 $LCS$ 长度，易得状态转移方程：

• 如果两个序列没有新的相同元素

  $dp[i][j] = \max(dp[i-1][j],dp[i][j-1])$

• 否则

  $dp[i][j]= \max(dp[i][j],dp[i-1][j-1]+1)$

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

#include <iostream>
using namespace std;
const int maxn = 1e4 + 5;

int a[maxn], b[maxn], f[maxn][maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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++) {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }
    }
    cout << f[n][n] << "\n";
    return 0;
}

由于时间复杂度中惨了一份平方，所以说在大多数题目下都不适用，此时考虑进行优化。试着将 $LCS$ 问题转换成 $LIS$ 问题，因为我们两个排列，而排列中的所有元素均不相同，因此可以根据其出现的位置，把元素重新编号。

解释：

因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后。

—— 离散小波变换

时间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for (int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n;
    unordered_map<int, int> mp;
    rep(i, 1, n) cin >> x, mp[x] = i;
    vector<int> L;
    rep(i, 1, n) {
        cin >> x;
        if (!mp.count(x))
            continue;
        int s = mp[x];
        auto it = lower_bound(L.begin(), L.end(), s);
        if (it == L.end())
            L.push_back(s);
        else
            *it = s;
    }
    cout << L.size() << '\n';
    return 0;
}

注意：

• map 的常数稍大，可以考虑 unordered_map 来解决问题，在洛谷模板题中，后者比前者快了 $50\%$ 。