CF10D LCIS[动态规划]

$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(dp[i-1][j], dp[i-1][j])$dp[i,j]=max(dp[i−1][j],dp[i−1][j])

但这是错误的, 因为还要求单调递增, 于是为了方便转移, 需要额外一个维度来保证正确性?
设 $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∈(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∈(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;
}