$LCIS$LCIS

Description

链接
给出两个长度分别为 $N,M$N,M的数列, 求最长上升公共子序列的长度

Solution

设阶段为 $i,j$i,j 表示第一个串前 $i$i个元素与第二个串前 $j$j个元素 $LCIS$LCIS
根据 $LCS$LCS的转移方程, 初步得出 :

$if(A_i==B_i)$if(Ai​==Bi​). $dp[i,j]=dp[i-1][j-1]+1$dp[i,j]=dp[i−1][j−1]+1
$else$else. $dp[i,j]=max\left(dp\right[i-1\left]\right[j],dp[i\left]\right[j-1\left]\right)$dp[i,j]=max(dp[i−1][j],dp[i][j−1])

但这是错误的, 因为还要求单调递增, 于是为了方便转移, 需要额外一个维度来保证正确性?
设 $dp[i,j,k]$dp[i,j,k] 表示第一个串前 $i$i项与第二个串前 $j$j项 $LCIS$LCIS且最后一个元素为 $k$k
可以初步得到

$if(A_i==B_j)$if(Ai​==Bj​). $dp[i,j,B_j]=dp[i-1,j-1,B_p]+1$dp[i,j,Bj​]=dp[i−1,j−1,Bp​]+1. $\{p\in (0,j),B_p\&lt;k\}${p∈(0,j),Bp​<k}
$else$else. $dp[i,j,k]=dp[i-1,j,k]$dp[i,j,k]=dp[i−1,j,k]

然而上方的愚蠢行为不知道会引起多少人笑话…
完全可以不要第3维:

$if(A_i==B_j)$if(Ai​==Bj​). $dp[i,j]=dp[i-1,p]+1$dp[i,j]=dp[i−1,p]+1. $\{p\in (0,j),B_p\&lt;k\}${p∈(0,j),Bp​<k}
$else$else. $dp[i,j]=dp[i,j-1]$dp[i,j]=dp[i,j−1]

由于最后要输出方案, 所以使用 $Pre$Pre数组记录最优转移来源, 最后递归输出即可

Code

#include<bits/stdc++.h>
#define reg register

const int maxn = 505;

int N;
int M;
int A[maxn];
int B[maxn];
int dp[maxn][maxn];
int Pre[maxn][maxn];

void print(int x){
        if(!x) return ;
        print(Pre[N][x]);
        printf("%d ", B[x]);
}

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]);
        scanf("%d", &M);
        for(reg int i = 1; i <= M; i ++) scanf("%d", &B[i]);
        for(reg int i = 1; i <= N; i ++){
                int maxx = 0, pre = 0;
                for(reg int j = 1; j <= M; j ++){
                        if(A[i] == B[j]){
                                if(dp[i][j] < maxx + 1){
                                        dp[i][j] = maxx + 1;
                                        Pre[i][j] = pre;
                                }
                        }
                        else{
                                dp[i][j] = dp[i-1][j];
                                Pre[i][j] = Pre[i-1][j];
                        }
                        if(B[j] < A[i] && maxx < dp[i-1][j]) maxx = dp[i-1][j], pre = j;
                }
        }
        int Ans = 0, Ans_p = 0;
        for(reg int i= 1; i <= M; i ++)
                if(Ans < dp[N][i]) Ans = dp[N][i], Ans_p = i;
        printf("%d\n", Ans);
        print(Ans_p);
        return 0;
}