最长公共上升子序列

定义

两个或者两个以上序列的所有共同上升子序列最长的一个，称为最长公共上升子序列(Longest Common Increasing Subsequence)。

求解算法

思路

设\(a[1\ldots n]\)、\(b[1\ldots m]\)表示原序列，\(f[i][j]\)表示\(a[1\ldots i]\)和\(b[1\ldots j]\)的LCIS； 状态转移方程： \[f[i][j]=\begin{cases} f[i-1][j],\quad a[i]\neq b[j] \ max\{f[i-1][k]\}+1,\quad 1\leq k\leq j,\quad a[i]=b[j] \end{cases} \] 答案为\(f[n][m]\)。 优化：对于\(max\{f[i-1][k]\}\)，可以用一个变量\(\_max\)记录，省去每次转移时重新遍历的复杂度。 可以在更新时用链表维护一下，以便输出LCIS。

实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2005;
int lena,lenb,a[MAXN],b[MAXN],ans1,ans2[MAXN];
struct node
{
    int x,nextx,nexty;
}f[MAXN][MAXN];
int main()
{
    scanf("%d",&lena);for(int i=1;i<=lena;++i)scanf("%d",&a[i]);
    scanf("%d",&lenb);for(int i=1;i<=lenb;++i)scanf("%d",&b[i]);
    swap(a,b);
    int t=lena;lena=lenb;lenb=t;
    for(int i=1;i<=lena;++i)
    {
        node _max=(node){0,0,0};
        for(int j=1;j<=lenb;++j)
        {
            f[i][j]=(node){f[i-1][j].x,i-1,j};
            if(b[j]<a[i]&&f[i-1][j].x>_max.x)_max=(node){f[i-1][j].x,i-1,j};
            else if(a[i]==b[j])f[i][j]=(node){_max.x+1,_max.nextx,_max.nexty};
        }
    }
    int k1=0,k2;
    for(int i=1;i<=lenb;++i)
    {
        if(f[lena][i].x>k1)
        {
            k1=f[lena][i].x;
            k2=i;
        }
    }
    printf("%d\n",k1);
    int x=lena,y=k2;
    while(x&&y)
    {
        node temp=f[x][y];
        if(f[temp.nextx][temp.nexty].x==temp.x-1)ans2[++ans1]=a[x];
        x=temp.nextx;y=temp.nexty;
    }
    for(int i=ans1;i>=1;--i)printf("%d ",ans2[i]);
    puts("");
    return 0;
}