思路:
表示与可以构成以为结尾的的长度。
当时,
当时,,显然需要满足,因为是以为结尾的。
最后枚举为结尾的的长度,找最大的。
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; }