题目描述

输入

输出

样例输入

5

1 4 5 2 3

3 4 2 1 5

样例输出

3

数据范围

样例解释

解法

模型显然。

设第一列为a[]，第二列为b[]，f[i]为前i个数的最大答案。

顺序枚举a，则f[i]=max(f[k]+1)(b[k]<b[i])。

最长不下降子序列。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) int(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="aP2.in";

const char* fout="aP2.out";

const int inf=0x7fffffff;

const int maxn=100007,maxt=maxn*4;

int n,i,j,k,ans;

int f[maxn],c[maxt];

int tong[maxn];

int a[maxn];

void change(int l,int r,int t,int v,int v1){

    int mid=(l+r)/2;

    if (l==r){

        c[t]=max(c[t],v1);

        return;

    }

    if (v<=mid) change(l,mid,t*2,v,v1);

    else change(mid+1,r,t*2+1,v,v1);

    c[t]=max(c[t*2],c[t*2+1]);

}

int getmax(int l,int r,int t,int v1,int v2){

    int mid=(l+r)/2;

    if (l>v2 || r<v1) return 0;

    if (l>=v1 && r<=v2) return c[t];

    return max(getmax(l,mid,t*2,v1,v2),getmax(mid+1,r,t*2+1,v1,v2));

}

int main(){

    scanf("%d",&n);

    for (i=1;i<=n;i++) scanf("%d",&j),tong[j]=i;

    for (i=1;i<=n;i++) scanf("%d",&j),a[i]=tong[j];

    for (i=1;i<=n;i++){

        f[i]=getmax(1,n,1,a[i]+1,n)+1;

        change(1,n,1,a[i],f[i]);

        ans=max(ans,f[i]);

    }

    printf("%d",ans);

    return 0;

}