闫式dp法
状态表示:
- 1~i与0~j的序列中以b[j]结尾的最长公共上升子序列
状态转移:
-
不包含a[i]的子集,最大值是f[i - 1][j];
-
包含a[i]的子集,f[i][j]是以b[1~j]结尾的最长上升公共子序列的最大值
优化:
当子集包含a[i]时需要来回遍历寻找以b[1~j]结尾的最长上升公共子序列的最大值,所以不如设置一个变量边循环边计算,从而减少一层循环,而此值等价于······讲不清,怎么说才能通俗易懂呢······
这个变量就是a[1]~a[i-1]与b[1]~b[1],b[1]~b[2]····b[1]~b[j]中的所有公共上升子序列中的序列的最大值小于a[i]的序列的长度+1;
这样后就可以更新之后枚举到的与a[i]值相等的元素
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],b[N],f[N][N],up[N],l;
int main()
{
int n,mx=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 maxn=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],maxn);
if(a[i]>b[j]) maxn=max(maxn,f[i-1][j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}