本题把$LIS$问题和$LCS$问题相结合,
状态表示中$f[i][j]$表示由$a$的前$i$个数,$b$的前$j$个数,且以$b[j]$结尾的最长公共上升子序列。
其状态计算分为两种:
- $f[i-1][j]$:不包含a[i]的选法(a[i]!=b[j])
- $f[i-1][k]+1$:包含a[i]的选法(a[i]=b[j])
于是就有了朴素版本:
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N],b[N];
int f[N][N];
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++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j])
{
int maxv=1;
for(int k=1;k<j;k++)
if(b[k]<a[i]) maxv=max(maxv,f[i-1][k]+1);
f[i][j]=maxv;
}
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
}
可以看到,朴素版本中
for(int k=1;k<j;k++)
if(b[k]<a[i]) maxv=max(maxv,f[i-1][k]+1);
这一段代码所求的是小于a[i]
的,最长公共子序列的最大值,
maxv
所表示的是一段前缀的最大值。
于是我们可以发现,我们可以把maxv
提出,在第二重循环中边循环边求其值,具体的优化代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N],b[N];
int f[N][N];
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 maxv=1;
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],maxv);
if(a[i]>b[j]) maxv=max(maxv,f[i-1][j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
}
而在这个优化版本中,我们可以发现,第一层循环只依赖它的上一次循环,所以我们可以用滚动数组来优化空间:
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N],b[N];
int f[N];
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 maxv=1;
for(int j=1;j<=n;j++)
{
if(a[i]==b[j]) f[j]=max(f[j],maxv);
if(a[i]>b[j]) maxv=max(maxv,f[j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i]);
cout<<res;
}
那么这就是这道题的最终代码。