[2019 CSP-S赛前集训] [CF10D] [蒟蒻Xx_queue学DP] 1.LCIS

题目链接:https://www.luogu.org/problem/CF10D

题目大意:本题是LCS和LIS的综合.给出两个序列,长度n,m(n,m<=500),求两个序列的最长公共上升子序列.

分析:先回顾一下LIS,与LCS的状态与方程表示方法,不知道的小伙伴先百度一下;

考虑涉及状态,\(F[i][j]\)表示两个序列能构成的以\(B_j\)结尾的LCIS的长度;

方程不难想出(其实对我来说还是有难度的):

\[ F[i][j](x)=\left\{ \begin{aligned} F[i-1][j] & & {A_i≠B_j}\max \{F[i-1][k] \}+1,0?k<j,B_k<A_i & & {A_i=B_j}\\end{aligned} \right. \]

这里解释一下这两个方程:

\(if(A_i!=B_j)\): \(i\)之前的以\(B_j\)结尾的最长公共上升子序列还是原来的那个(因为现在的A_i与B_j不相等嘛,加入了A_i也不能构成新的序列(不公共))，所以长度还是f[i?1][j];

\(if(A_i==B_j)\):这时候两者相等了,出现了一个新的公共元素\(A_i\),将\(A_i\)放到原最长公共上升子序列的尾部,看看能不能继续满足上升这一条件,所以我们可以枚举一个\(k\),如果\(B_k<A_i\),就放进去并加上1。

这里有一个地方要注意:先要初始化\(A_0=B_0=-inf\),思考为什么?

如果不初始化一下,你最开始的第一个元素就有可能检测不到而漏掉,所以这里\(k\)也要从0开始枚举;

不信你可以去试试\(k\)从1枚举,第二个样例就会WA;

所以剩下的就很容易了!直接\(O(n^3)\)枚举i,j,k,按照方程来写就over;

最后输出序列时递归地按照转移方程输出,注意一下边界条件;

AC代码:(请理解上述文字后再看代码,请勿直接抄袭)

本代码递归输出的部分参考了博客:https://blog.csdn.net/C20191904/article/details/81461973,这里作出声明;

#include <bits/stdc++.h>
#define N (500+5)
using namespace std;
int n,m,Max,x,y;
int a[N],b[N],dp[N][N];
void print_ans(int x,int y){
    if(dp[x][y]==1){
        printf("%d ",b[y]);
        return;
    }
    if(!x||!y) return;
    if(dp[x][y]==dp[x-1][y]){
        print_ans(x-1,y);
        return;
    }
    for(int i=y-1;i>=1;i--){
        if(b[i]<b[y]&&dp[x][y]==dp[x-1][i]+1){
            print_ans(x,i);
            printf("%d ",b[y]);
            return;
        }
    }
}
int main(){
    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]);
    }
    a[0]=b[0]=INT_MIN;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                for(int k=0;k<j;k++){
                    if(b[k]<a[i]){
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
                    }
                }
                if(Max<dp[i][j]) Max=dp[i][j],x=i,y=j;
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    printf("%d\n",Max);
    print_ans(x,y);
    return 0;
}