图片说明

思路:

表示可以构成以为结尾的的长度。
时,
时,,显然需要满足,因为是以为结尾的。
最后枚举为结尾的的长度,找最大的。

MyCode:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[3005],b[3005],f[3005][3005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    for(int i=1;i<=n;++i) {
        int val(0);
        for(int j=1;j<=n;++j) {
            if(a[i]==b[j]) f[i][j]=val+1;
            else f[i][j]=f[i-1][j];
            if(b[j]<a[i]) val=max(val,f[i-1][j]);
        }
    }
    int ans(0);
    for(int i=1;i<=n;++i) ans=max(ans,f[n][i]);
    cout<<ans<<'\n';
    return 0;
}