lg1439

发表于 | 分类于 | 阅读数 次

链接:lg1439

题解

  • 注意是n的全排列，所以用a串作为字典串将b串更改一下,例如a串3 2 1 4 5 b串1 2 3 4 5
  • 更改之后b串变为3 2 1 4 5 ，求最长公共子序列变为求新b串的最长上升子序列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e5+7;
    const int inf=0x3f3f3f3f;
    template <typename T>inline void read(T &x){
        char c;int sign=1;x=0;
        do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
        do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
        x*=sign;
    }
    int id[N],a[N],n,dp[N],ans;
    int main(){
        read(n);
        int x;
        memset(dp,0x3f,sizeof dp);dp[0]=0;
        rep(i,1,n){read(x);id[x]=i;}
        rep(i,1,n){read(x);a[i]=id[x];}
        rep(i,1,n){
            if(a[i]>dp[ans])dp[++ans]=a[i];
            else {
                int k=lower_bound(dp+1,dp+ans+1,a[i])-dp;
                dp[k]=min(dp[k],a[i]);
            }
        }
        printf("%d\n",ans);
        return 0;
    }