• 前言
• 题目大意
• 思路
• 代码
  *
  • lower_bound版:
  • 二分版：
• 总结

前言

本题的 $n^2$ 做法挺好想的，关键在于怎么降低时间复杂度。

题目大意

求两个序列的LCS，两个序列分别是 $1～n$ 的全排列。

思路

$\mathcal{O}(n^2)$ 的做法不说了，本题的关键之处在于映射。

我们让 $a$ 数组不再是原来的 $a$ 数组，而是 $A[a[i]]=i$，这样就变成了求 $b$ 在 $a$ 的映射中的最长上升子序列。

why?一脸问号

3 2 1 4 5
1 2 3 4 5

映射了之后变成：

由于b也要映射，这里 $a$ 就是 $A$，$b$ 是 $A$ 中的映射。

1 2 3 4 5
3 2 1 4 5

由于 $a$ 是有序的，$b$ 的元素又跟 $a$ 一样，那么只要 $b$ 有一个子序列递增，它就一定也是新 $a$ 的子序列。由于要最大，那么就是求一个最长上升子序列。

之后 $\mathcal{O}(n\log{n})$ 求一下最长上升子序列就好。

代码

lower_bound版:

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,A,b,dp[MAXN],a[MAXN];
int main(){
    scanf("%lld",&n);
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&A);
        a[A]=i;
    }
    ll ans=0;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&b);
        if(a[b]>dp[ans]){
            dp[++ans]=a[b];
        }else{
            ll num= lower_bound(dp+1,dp+n+1,a[b])-dp;
            dp[num]=a[b];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

二分版：

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,A,b,dp[MAXN],a[MAXN];
int main(){
    scanf("%lld",&n);
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&A);
        a[A]=i;
    }
    ll ans=0;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&b);
        if(a[b]>dp[ans]){
            dp[++ans]=a[b];
        }else{
            ll l=1,r=ans,num=0;
            while(l<=r){
                ll mid=(l+r)>>1;
                if(dp[mid]<=a[b]){
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
            dp[l]=a[b];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

总结

本题的关键点就在于利用了元素相同和映射关系的技巧。