最长公共上升子序列(LICS)

我们学过最长升序列(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的定义:F[i][j]表示A的第i位及之前 的子序列与 B的第j位及之前 的子序列,这两段序列的LCS长度。注意,A中1到i段与B中1到j段LCS不一定取了i或j。这就很麻烦了:如何判断下一个取的元素大于LCS的最后一个元素,也就是如何判断取下一个元素后序列是不是升的呢?这时候不得不重新考虑DP的定义了。

由于要标记LCS的最后一个元素,不妨像LIS一样,定义F[i][j]表示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,因为如果取F[i-1][j-1]意味着j-1必取了。所以应该枚举一个k∈[1,j-1],在F[i-1][k]中取最大值+1就是F[i][j]了。
2. A[i]<B[j]:由于B[j]是最后一个,所以不能直接像LCS一样F[i][j]=max(F[i-1][j],F[i][j-1]);应该是F[i][j]=F[i-1][j],因为这时求得的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]<b[j] && 1≤k≤j-1)

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

如何优化成O(N²)?

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

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

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

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

#include<cstdio>
#include<iostream>
#include<cstring>
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]<a[i+1]) lst[j-1]=max(lst[j-2],f[i][j-1]);
                    else lst[j-1]=lst[j-2];
                }
                if (f[i][j]>ans) ans=f[i][j];
            }
            if (b[m]<a[i+1]) lst[m]=max(lst[m-1],f[i][m]); else lst[m]=lst[m-1];
        }
        printf("%d\n",ans);
        if (t) printf("\n"); 
    }
    return 0;
}
本文采用 BY-NC-SA 4.0 协议,欢迎转载。如有错误欢迎指出。
本文链接: https://skywt.cn/posts/lics/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。