样例
4
2 2 1 3(a)
2 1 2 3(b)
输出
2
原因
a[3]和a[4]与b[2]和b[4]属于最长公共上升子序列,所以最大是2
AC板子(On^2)+注释
#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;//这里的maxv是用来存放下一次a[i]和b[j]相同前的前导最长公共上升子序列。
for(int j=1;j<=n;j++){//On^2扫描
f[i][j]=f[i-1][j];//f[i][j]先吃f[i-1][j]的状态表明当a[i]不属于公共上升子序列时。
if(a[i]==b[j])f[i][j]=max(f[i][j],maxv);//a[i]属于公共上升子序列时,自然a[i]=b[j],因为两个同属于公共上升子序列,且都是最后一个元素。
if(b[j]<a[i])maxv=max(maxv,f[i-1][j]+1);//重点!如果b[j]<a[i]那么为下次b[j]=a[i]做前导准备,也就是说如果后续
}//有a[i]==b[j],那么自然f[i-1][j]也是一种情况,为了避免重复比较,将其与maxv进行比较,更新maxv,maxv存储前导最长公共子序列。
}
int res=0;
for(int i=1;i<=n;i++){//为什么要全扫描一遍呢?因为最长的公共上升子序列不一定是以n为结尾的最长公共子序列
res=max(res,f[n][i]);//所以需要扫描求取最长的公共上升子序列。
}
cout<<res<<endl;
return 0;
}
总结
我对于 LCIS 的优化写法的总结是:
1:考虑a中前i个数字,b中前j个数字,且当前以b[j]结尾的子序列的方案。
2:每次f[i][j]的状态更新从公共上升子序列包含a[i]和不包含a[i]来更新
3:将第三重O(n)复杂度压为O(1),通过避免重复计算前导maxv来降低复杂度,通过maxv来更新前导最大公共上升子序列,
降低复杂度。