求赞!
dp暴力:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,a[N],b[N],dp[N][N],ans;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(ll i=1; i<=n; i++) cin>>a[i];
for(ll i=1; i<=n; i++) cin>>b[i];
for(ll i=1; i<=n; i++)
for(ll j=1; j<=n; j++)
if(a[i]==b[j]) {
dp[i][j]=1;
for(ll k=1; k<j; k++)
if(b[k]<b[j]) dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
} else dp[i][j]=dp[i-1][j];
for(ll i=1; i<=n; i++) ans=max(ans,dp[n][i]);
cout<<ans;
return 0;
}
dp优化:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3010;
int n,a[N],b[N],dp[N][N],ans;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
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 mx=0;
for(int j=1; j<=n; j++) {
if(a[i]==b[j]) dp[i][j]=mx+1;
else dp[i][j]=dp[i-1][j];
if(b[j]<a[i]) mx=max(mx,dp[i-1][j]);
}
}
for(int i=1; i<=n; i++) ans=max(ans,dp[n][i]);
cout<<ans;
return 0;
}