C++14(g++5.4) 解法, 执行用时: 26ms, 内存消耗: 23992K, 提交时间: 2020-09-15 21:03:11

#include<bits/stdc++.h>
using namespace std;
int a[3010],b[3010],dp[3010][3010];
int main(){
	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])  dp[i][j]=val+1;
			else  dp[i][j]=dp[i-1][j];
			if(b[j]<a[i]) val=max(val,dp[i][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)  ans=max(ans,dp[n][i]);
	cout<<ans<<endl;
	return 0;
}

C++ 解法, 执行用时: 17ms, 内存消耗: 420K, 提交时间: 2022-01-09 17:22:29

#include<bits/stdc++.h>
using namespace std;
int a[3001],b[3001],f[3001],maxx,n;
int main(){
    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++){maxx=0;for(int j=1;j<=n;j++){if(a[i]>b[j]&&maxx<f[j])maxx=f[j];if(a[i]==b[j])f[j]=maxx+1;}}
    maxx=0;
    for(int i=1;i<=n;i++)maxx=max(f[i],maxx);
    cout<<maxx;
    return 0;
}