P1439 【模板】最长公共子序列

首先找最大公共子序列，可以轻松想到 $O(n^2)$ 的 dp 转移式子，$f_{i,j}=max\begin{cases}f_{i-1,j}&i>0\
f_{i,j-1}&j>0\
f_{i-1,j-1}+1&i>0,j>0,A_i=A_j
\end{cases}$

但是我们发现最后 $n\le10^5$ 所以 $n^2$ 的复杂度不够优，这个时候再看题目，发现 A，B 都是 1~n 的排列，由此可知 A，B 中每个 1~n 之间的数都有且仅有一个，而最大公共子序列就是 A，B 中最大的相同的子序列，那么当我们把所有 $B_i$ 改为 $B_i$ 在 A 中的位置，那么要求的 A，B 最大公共子序列实际就是现在的 B 中的最大上升子序列。

求最大上升子序列，有一种 $O(n\log_2n)$ 的方法。

for (int i = 1;i <= n; ++ i)//n为a的长度
    f[i] = 2e9 + 7;     //f[i]是长度为i的上升子序列的最后一个值
f[1] = a[1];
int len = 1;
//初始化
for (int i = 1;i <= n; ++ i) {
    if (a[i] > f[len]) {
        f[++ len] = a[i];
        continue;
    }
    int l = 0, r = len, mid;
    while (l <= r) {
        mid = l + r >> 1;
        if (f[mid] >= a[i]) r = mid - 1;
        else l = mid + 1;
    }
    if (a[i] < f[l]) f[l] = a[i];
}

分析：当 $a_i$ 比 $f_i$ 的最大小的话，那么它替掉那个数不会影响后面的贡献。

所有本题就可以用 $O(nlog_2n)$ 的复杂度解决。

#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int mp[N];
int f[N], n, maxn[N];
int main() {
    scanf ("%d", &n);
    for (int i = 1;i <= n; ++ i) {
        int tmp;
        scanf ("%d", &tmp);
        mp[tmp] = i;
    }
    for (int i = 1;i <= n; ++ i) {
        int tmp;
        scanf ("%d", &tmp);
        a[i] = mp[tmp];
    }
    for (int i = 1;i <= n; ++ i)
        f[i] = 2e9 + 7;
    f[1] = a[1];
    int len = 1;
    for (int i = 1;i <= n; ++ i) {
        if (a[i] > f[len]) {
            f[++ len] = a[i];
            continue;
        }
        int l = 0, r = len, mid;
        while (l <= r) {
            mid = l + r >> 1;
            if (f[mid] >= a[i]) r = mid - 1;
            else l = mid + 1;
        }
        if (a[i] < f[l]) f[l] = a[i];
    }
    printf ("%d\n", len);
    return 0;
}