题目链接

Solution

动态规划.

令 \(f_{i,j}\) 表示 \(a\) 数组前 \(i\) 个和 \(b\) 数组前 \(j\) 所得的最长的 LCIS .

转移很好想:

\(a_i!=b_j :~f_{i,j}=f_{i-1,j}\)

\(a_i==b_j :~f_{i,j}=max(f_{i-1,j},f_{i,t(存储位置)}+1)\)

然后最后面 \(f[n][i]\) 中的最大值即为答案.

Code

#include<bits/stdc++.h>

int n,a[502],b[502];

int f[502][502],g[502][502];

void Print(int p) {

    if(!p)

        return ;

    Print(g[n][p]);

    printf("%d ",b[p]);

}

int main() {

    int m,p=0;

    scanf("%d",&n);

    for(int i=1;i<=n;++i)

        scanf("%d",a+i);

    scanf("%d",&m);

    for(int i=1;i<=m;++i)

        scanf("%d",b+i);

    for(int i=1,t=0;i<=n;++i,t=0)

        for(int j=1;j<=m;++j) {

            f[i][j]=f[i-1][j];

            g[i][j]=g[i-1][j];

            if(a[i]==b[j]&&f[i-1][t]+1>f[i][j]) {

                f[i][j]=f[i-1][t]+1;

                g[i][j]=t;

            }

            if(b[j]<a[i]&&f[i-1][j]>f[i-1][t])

                t=j;

        }

    for(int i=1;i<=m;++i)

        if(f[n][i]>f[n][p])

            p=i;

    printf("%d\n",f[n][p]);

    Print(p);

    return 0;

}