题目描述

无描述

算法：

我也不知道
都在注释里了

#include<cstdio>
#include<cmath>

using namespace std;

const int N=3010;

int n,a[N],b[N];
int f[N][N];
//f[i][j]表示a[i]与b[j]中
//以b[j]结尾的最长公共上升子序列

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         //1.若该序列不存在a[i],则f[i][j]=f[i-1][j];
    //         //2.若该序列存在a[i],即a[i]==b[j],f[i][j]=max{f[i-1][k]+1},k∈[1,j-1],且b[k]<b[j]
    //         //两种情况取max
    //         f[i][j]=f[i-1][j];
    //         if(a[i]==b[j]){
    //             int maxn=1;
    //             for(int k=1;k<j;k++)
    //                 if(b[k]<b[j])
    //                 maxn=max(maxn,f[i-1][k]+1);
    //             f[i][j]=max(f[i][j],maxn);
    //         }
    //     }
    // }
    //对代码进行等价变换
    for(int i=1;i<=n;i++){
        int maxn=1;
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])f[i][j]=max(maxn,f[i][j]);
            //maxn存f[i-1][k]中的最大值
            //由于是求最大值，每次更新maxn即可
            if(b[j]<a[i])maxn=max(maxn,f[i-1][j]+1);
        }
    }
    int res=1;
    for(int i=1;i<=n;i++)
        res=max(res,f[n][i]);
    printf("%d\n",res);
    return 0;
}