我们学过最长升序列(Longest Increasing Subsequence,简称LIS)最长公共子序列(Longest Common Subsequence,简称LCS)(没错之前两篇博客就是为这篇准备的……),那么如果我们要求最长公共上升子序列(Longest Increasing Common Subsequence,简称LICS或者LCIS)呢?

(建议阅读本文之前先看看LCS。)

例题:Greatest Common Increasing Subsequence (HDU)

O(N³)的动态规划

一开始想到的肯定是结合LIS和LCS,如何结合?回忆一下LCS的定义:Fi表示A的第i位及之前 的子序列与 B的第j位及之前 的子序列,这两段序列的LCS长度。注意,A中1到i段与B中1到j段LCS不一定取了i或j。这就很麻烦了:如何判断下一个取的元素大于LCS的最后一个元素,也就是如何判断取下一个元素后序列是不是升的呢?这时候不得不重新考虑DP的定义了。

由于要标记LCS的最后一个元素,不妨像LIS一样,定义Fi表示A的第i位及之前 的子序列与 B的第j位及之前 的子序列,这两段序列的LCS长度,其中B[j]是LCS的最后一个元素。与LCS一样枚举i、j,讨论几种情况:

  1. A[i]>B[j]:既然这位上可以取,因为第一维定义时没有规定A[i]必取,所以之前的LICS长度第一维必然是i-1;然而第二维规定了B[j]必取,所以LICS长度第二维不一定是j-1,因为如果取Fi-1意味着j-1必取了。所以应该枚举一个k∈[1,j-1],在Fi-1中取最大值+1就是Fi了。
  2. A[i]<B[j]:由于B[j]是最后一个,所以不能直接像LCS一样Fi=max(Fi-1,Fi);应该是Fi=Fi-1,因为这时求得的LCS根本没变,B[j]一定与A[1...i-1]中一个元素相等,不考虑A[i]照样能得出最优解。
    所以得出转移方程:
F[i][j]=F[i-1][j];        (a[i]≤b[j])
F[i][j]=max(F[i-1][k])+1; (b[k]

这样写的时间复杂度是O(N³),(在上面那道例题中)似乎并不能达到满分。能不能优化呢?

如何优化成O(N²)?

仔细观察,这个DP慢就慢在k这层循环。如果我们把k这层循环拿掉该多好!(因为N²个子问题是不可避免的,所以只能优化这层循环……)观察转移方程,如果我们能把max(Fi-1)+1提前处理出来就好了!但是有个重要的条件:b[k]<b[j]。k在不断变化,j也在不断变化,有这个条件的限制就难以构造了……

看看前面,a[i]=b[j]!所以这个条件就变成b[k]<a[i]!
我们在外层循环枚举i,在里面一层循环求答案只与i-1有关,i就相当于是不再变化的!这样就可以构造个lst数组(last的缩写),存储max(Fi-1),也可以判断这个条件了!

lst[j-1]=max(lst[j-2],f[i][j-1]); (b[j-1]<a[i+1])
lst[j-1]=lst[j-2];                (b[j-1]≥a[i+1])

加上这个优化,这题就能AC了~贴上代码:

#include
#include
#include
using namespace std;
const int maxn=505;
int t,n,m,a[maxn],b[maxn],f[maxn][maxn],lst[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline int max(int x,int y){
    if (x>y) return x; else return y;
}
int main(){
    freopen("lics.in","r",stdin);
    freopen("lics.out","w",stdout);
    t=read();
    while (t--){
        n=read();
        for (int i=1;i<=n;i++) a[i]=read();
        m=read();
        for (int i=1;i<=m;i++) b[i]=read();
        int ans=0;
        memset(f,0,sizeof(f));memset(lst,0,sizeof(lst));
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                if (a[i]==b[j]) f[i][j]=lst[j-1]+1; else f[i][j]=f[i-1][j];
                if (j!=1){
                    if (b[j-1]ans) ans=f[i][j];
            }
            if (b[m]