朴素版比较容易懂,优化版需要想想。
C++代码朴素版
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int const maxn=3010;
int a[maxn];
int b[maxn];
int f[maxn][maxn];
int main(void)
{
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++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j])
{
f[i][j]=max(f[i][j],1);///空集
for(int k=1;k<j;k++)
if(b[k]<b[j])
f[i][j]=max(f[i][j],f[i][k]+1);
}
}
}
int res=0;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}
C++ 代码优化版
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int const maxn=3010;
int a[maxn];
int b[maxn];
int f[maxn][maxn];
int main(void)
{
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;//存dp[i-1][1]到dp[i-1][j-1]的最大值
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];//没有a[i]
if(a[i]==b[j])
{
f[i][j]=max(f[i][j],val+1); //取max(f[k]+1,f[i][j])比较
}
//更新最大值,如果当前以b[j]结尾的数小于a[i],则不满足定义,更新最大值
if(b[j]<a[i]) val=max(val,f[i][j]);
}
}
int res=0;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}
普通版没想懂,求高数大佬解释一下