tyvj1071 LCIS 最长公共上升子序列

tyvj1071 LCIS 最长公共上升子序列


题目链接

题意

给定两个长度为 n (正)整数序列A,B,你需要给出它们的最长公共上升序列的长度

数据范围

n \in [1,3000]

样例
  • input

4

2 2 1 3

2 1 2 3

  • output

2


分析

单独的LCS和LIS问题我们已经十分熟悉了,对于LCS我们用 dp[i][j] 表示A前 i 位与B前 j 位的LCS最长长度或者毒瘤映射法,对于LIS我们有 dp[i] 表示以 A[i] 结尾的LIS最长长度或优化的 O(nlogn) 算法。

LCIS问题把LCS和LIS问题结合起来了,因为有两个串,显然我们至少要用二维数组表示状态,比如可以 dp[i][j] 表示A前 i 位与B前 j 位的LCIS最长长度。

这种思想是从LCS问题继承而来的 ,因此它可以解决LCIS中的LCS部分,考虑如何用它来解决LIS部分。

显然目前我们对状态的定义不能解决LIS部分, dp[x][y] 仅仅保存了前 xy 位这个范围内的情况,也就是说这种状态定义没有一个确定的结尾元素 ,没有这个重要的信息我们就无从知道这个序列的末尾元素是否比当前处理到的元素 A[i] (B[i]=A[i])小,即不能确定是否满足上升的要求,导致无法转移。

既然这样,我们就重新定义状态,想办法保留一个结尾信息(我们不必保存两位,因为是公共子序列)。

求解

状态定义: 在LCS基础上,我们仿照LIS的状态定义,定义 dp[i][j] 表示A序列前 i 位和B序列前 j 位构成的以B序列第 j 位结尾的LCIS最长长度

状态转移:

dp[i][j] \space = \space dp[i – 1][j] \space \space \space (A[i] \space \neq \space B[j])

dp[i][j] \space = \space dp[i – 1][k] \space + \space 1 \space \space (k \in [0,j) && A[i] = B[i])

代码:

#include <iostream>
#include <cstdio>


const int MAXN = 3007;
int A[MAXN], B[MAXN], dp[MAXN][MAXN];


int main() {
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &B[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i] == B[j]) {
                for (int k = 0; k < j; ++k) {
                    if (B[k] < B[j]) {
                        dp[i][j] = std::max(dp[i][j], dp[i - 1][k] + 1);
                    }
                }
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
            ans = std::max(ans, dp[i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}

这样做的时间复杂度是 O(n^{3}) ,在理论上无法通过 (然而我在tyvj上交了一发才跑了40ms,数据较弱)

优化

观察这个三层循环,当最外两层固定时,决策集合是满足 0\leq k < j B_{k} < B_{j} k (对应状态)的集合,而可以进行对答案产生贡献的转移的前提是 A[i] == B[j] ,所以决策集合的要求就等价与 0\leq k < j B_{k} < A_{i} 。在最外层固定时, A[i] 是固定的,所以我们在同一个 i 下维护的决策集合是可以被继承的

如果第二层循环中的 j 自增 1 ,我们的决策集合仅仅有可能增加一个 $k ,而上一个状态的决策集合仍然被继承下来(最外层相同),如果这个 k 被加入决策集合,那么在最外层不变的情况下,这个 k 也会被继承下去。

显然这个决策集合中的元素都可以用来进行状态转移,那么我们一定选择其中 dp[i – 1][k] 最大的一个进行转移。所以我们只要用一个值 maxn 维护这个集合中的 k 对应的 dp[i – 1][k] 的最大值就可以了,并且在转移之后判断是否满足 B[j] < A[i] ,然后用 dp[i – 1][j] 来更新 maxn 即可

状态转移: dp[i][j] \space = \space dp[i – 1][j] \space \space \space (A[i] \space \neq \space B[j])

dp[i][j] \space = \space maxn \space + \space 1 \space \space \space (A[i] == B[j])

决策集合维护: maxn \space = \space max(dp[i – 1][j], maxn) \space \space \space (B[j] \space < \space A[i])

代码:

#include <iostream>
#include <cstdio>


const int MAXN = 3007;
int A[MAXN], B[MAXN], dp[MAXN][MAXN];


int main() {
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &B[i]);
    }
    for (int i = 1; i <= n; ++i) {
        int maxn = 0;
        for (int j = 1; j <= n; ++j) {
            if (A[i] == B[j]) dp[i][j] = maxn + 1;
            else dp[i][j] = dp[i - 1][j];
            if (B[j] < A[i]) maxn = std::max(dp[i][j], maxn);
            ans = std::max(ans, dp[i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}

然而在实际评测中,我们的 O(n^{3}) 算法竟然比 O(n^{2}) 算法快!

我认为这是数据太水造成的,由于 A[i] == B[j] 的情况太少,导致 O(n^{3}) 没有卡出来

对于这种决策集合元素只增不减的dp,我们可以维护一个其中状态的最值而防止重复扫描


参考资料

《算法竞赛进阶指南》 李煜东 著

发表评论

电子邮件地址不会被公开。 必填项已用*标注