思路
f[i][j]:A串前i个,B串前j个 且以b[j]结尾的上升公共子序列 的集合
属性:maxlen
集合划分:
case 1:a[i]一定不在 最长上升公共子序列中
case 2:a[i]在 (前提是a[i]==b[j])
case 1 可以用 f[i-1][j] 表示
case 2继续分为以下情况:
1:不存在倒数第二个元素 --> 长度为1
2:存在倒数第二个元素 且 其在B串中为b[k](k在[1,j)) --> f[i-1][k]+1
综上:Code如下
朴素做法
$O(n^3)$
TLE !!!
#include <iostream>
using namespace std;
const int N=3010;
int a[N],b[N];
int f[N][N];
int 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++)
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(a[i]>b[k]) maxv=max(maxv,f[i-1][k]+1);
f[i][j]=max(f[i][j],maxv);
}
}
int res=-1;
for(int i=1;i<=n;i++) res=max(f[n][i],res);
cout<<res;
return 0;
}
优化做法
优化:
在枚举到 i,j 时,用到的maxv 是在i,j-1时得到的
根据这个性质 可以优化
$O(n^2)$
AC !!!
#include <iostream>
using namespace std;
const int N=3010;
int a[N],b[N];
int f[N][N];
int 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++){
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); --> maxv 由 上一个循环得到
if(a[i]>b[j]) maxv=max(maxv,f[i-1][j]+1);
}
}
int res=-1;
for(int i=1;i<=n;i++) res=max(f[n][i],res);
cout<<res;
return 0;
}