题解 CF10D 【LCIS】

花里心爱 · 2019-01-13 21:24:45 · 题解

题目要求我们求出两个串的最长公共上升子序列(LCIS)。

我们先回想一下LIS和LCS的求法。

LIS

给出一个长度为n的序列a，求一个最长的序列s，满足s为a的子序列且对于任意i<j，s[i] < s[j]。

我们设f[i]表示以a[i]结尾的LIS长度，设a[0]比序列中的任何数都小，对于每个f[i]，它可以从之前所有比a[i]小的数转移过来，结果取\max。

设f[0]=0，则

最终答案为每一个可能为a[i]结尾的LIS长度的最大值，即

如何记录答案序列？

开一个pre数组，每次更改状态的时候，将当前的pre值改为前一个数组下标。

最后的时候从最终的pre值向前回溯，开一个栈，把目标数字放在栈里逆序输出（因为我们回溯的过程相当于把整个序列反了过来）。

// ans 为答案，sp 为当前指向的位置，初始值均为0
    for(int i = 1; i <= n; ++j)
        if(ans < f[i]) {
            ans = f[i];
            sp = i;
        }
    printf("%d\n", ans);
    for(; sp; sp = pre[sp])
        st[++tot] = a[sp]; // 将要求的序列放入栈中
    while(tot) printf("%d ", st[tot--]); // 逆序输出

LCS

给出2个长度分别为n, m的序列a, b，求一个最长的序列s，满足s为a的子序列且s为b的子序列。

设f[i][j]表示在a的前i个数，b的前j个数中取出的LCS长度，对于每个f[i][j]，有3种情况：

1. 不选a[i]（但b[j]有可能已经选了），答案为f[i-1][j]。
2. 不选b[j]（但a[i]有可能已经选了），答案为f[i][j-1]。
3. 当a[i] = b[j]时，可以选a[i]（同时也是b[j]），答案为f[i-1][j-1]+1。

以上即

最终答案为每一个元素都可能取到的状态，即

LCIS

给出2个长度分别为n, m的序列a, b，求一个最长的序列s，满足s为a的子序列且s为b的子序列，且对于任意i<j，s[i] < s[j]。

像LCS一样，考虑设f[i][j]表示在a的前i个数，b的前j个数中取出的LCIS长度，但这样不好转移。

所以综合LIS的思想，设f[i][j]表示在a的前i个数中取出，且以b[j]结尾的LCIS长度。

设a[0] = b[0]且均比两个序列中的任何数都小，设f[0][0] = 0，则有2种情况：

1. 当a[i] \ne b[j]时，我们不能选a[i]（因为序列以b[j]结尾，所以b[j]必须选），答案为f[i-1][j]
2. 当a[i] = b[j]时，我们枚举b之前可能的结尾，检查能不能把a[i]（即b[j]）加入，答案为\displaystyle \max_{a[i] > b[k]} \{f[i-1][k]+1\},\quad 0 \leq k < j

最终答案为每一个可能为b[j]结尾的LIS长度的最大值，即

然后开一个pre数组记录答案，按照上面的方法记录。这时候我们要找的是以b[j]结尾的序列，寻找的时候如下：

for(int j = 1; j <= m; ++j)
        if(ans < f[n][j]) {
            ans = f[n][j];
            sp = j;
        }
    printf("%d\n", ans);
    for(; sp; sp = pre[n][sp])
        st[++tot] = b[sp];
    while(tot) printf("%d ", st[tot--]);

复杂度

时间复杂度为O(n^3)，空间复杂度为O(n^2)，可以通过本题。

实际上，因为对于每一个i，状态总是从i-1转移过来，所以空间复杂度可以优化到O(n)。（然而并没有什么意义）

总代码：

#include <cstdio>
#include <cctype>
#define maxn 505
inline int read() {
    int d=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){d=d*10+ch-48;ch=getchar();}return d;
}

int n, m, a[maxn], b[maxn];
int f[maxn][maxn], pre[maxn][maxn];
int ans, sp;
int st[maxn], tot;

int main() {
    n = read(); for(int i = 1; i <= n; ++i) a[i] = read();
    m = read(); for(int i = 1; i <= m; ++i) b[i] = read();
    a[0] = b[0] = -1;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j) {
        if(a[i] == b[j]) { // 可以将a[i]加入
            for(int k = 0; k < j; ++k)
                if(a[i] > b[k] && f[i][j] < f[i-1][k]+1) { // 这里a[i]既为b[j]
                    f[i][j] = f[i-1][k]+1;
                    pre[i][j] = k;
                }
        }
        else { // 不能加入a[i]
            f[i][j] = f[i-1][j];
            pre[i][j] = pre[i-1][j];
        }
    }
    for(int j = 1; j <= m; ++j) // 寻找 ans 及序列结尾所在的位置 sp
        if(ans < f[n][j]) {
            ans = f[n][j];
            sp = j;
        }
    printf("%d\n", ans);
    for(; sp; sp = pre[n][sp]) // 寻找整个序列
        st[++tot] = b[sp];
    while(tot) printf("%d ", st[tot--]);
    return 0;
}