题解 CF10D 【LCIS】

NashChen · 2019-08-06 12:16:53 · 题解

LCIS问题

Solution of LCIS Problem - By Nash

本文进行了路径保存方面的讨论。

upd.2021.8.10 初版编辑时各方面经验不足，现重新排版，小幅度重新组织语言

由于与初版编辑时间间隔相当长，如与现有题解重复请管理直接撤下。

【知识基础】

LCS (最长公共子序列, O(n^2))
LIS (最长上升子序列, O(n^2)，本题未用到 O(n\log n) 做法)

【题意简述】

求 A[1..N] 和 B[1..M] 两个数列的最长公共上升子序列

【状态设计】

设 LCIS(i,j) 为数列 A[1..i] 和 B[i..j] 的最长公共上升子序列。

仿照 LCS 问题，我们很容易想到直接表示出状态的设法：

f[i][j] = len(LCIS(i,j))

但这样我们在转移时无法获得 LCIS(i,j) 结尾位置的信息，也就无法像 LIS 问题那样枚举上一个 LIS 的结尾,通过将新的数接在后面来更新 LIS 。

于是，综合 LIS 的思想，我们限定 该 LCIS 以 B[j] 为结尾 。为方便讨论，记作 S(i,j)

这样，状态转移就更容易实现了。

【状态转移方程】

我们选择枚举当前状态 (i,j) ，采用的状态转移方式是 寻找子状态更新当前状态

若 A[i] \not= B[j]

因为要求 S(i,j) 是以 B[j] ，所以 S(i,j) 在 A[1..i] 中的末尾不为 A[i]

于是可得 f[i][j] = f[i-1][j]

若 A[i] = B[j]

在 S(i-1,k),(1\leq k<j) 中的某一个可以通过选择在后面增加一个 A[i] (即 B[j] ) 组成一个新的 LCIS.

在这些公共上升子序列中,选取一个最长的就是解

所以 f[i][j] = \max\{ f[i-1][k]+1 \mid 1\leq k<j ,B[k]<B[j]\}

总的方程就是

f[i-1][j] && (A[i]\not=B[j])\\ \max\{ f[i-1][k]+1 \mid 1\leq k<j ,B[k]<B[j]\} && (A[i]=B[j]) \end{cases}

最后的答案是

\max\{ f[N][j] \mid 1\leq j\leq M \}

时间复杂度 O(n^3)

【路径输出】

路径输出有两种方法，分别如下

方法1

假设我们直接开一个动态长度的数组(可以用vector) 储存 LCIS ，每次转移时进行更新。

具体来说，建立二维数组 lcis[1..M][]，

其中 lcis[j][1..f[i][j]] 用于储存上文提到的 S(i,j)

每次转移时将 lcis[k][1..f[i-1][k]] 完全复制到 lcis[j][1..f[i][j]-1] 上,

再在后面的 lcis[j][f[i][j]] 的位置增加一个 B[j].

最后找到 LCIS 最长的结束位置 ansj ,将 lcis[ansj][1..f[N][ansj]] 输出

这种方法中，由于多重 if 语句的限制,实际运行速度很快,

甚至可以通过 N=5000 的多组极端数据，但其时间复杂度上界仍为 O(n^3) 。

【核心代码1】

for (int i=1; i<=N; i++)
{
    for (int j=1; j<=M; j++)
    {
        if (A[i] == B[j])
        {
            f[i][j] = 1;
            lcis[j][1] = B[j];
            for (int k=1; k<j; k++)
                if (B[k]<B[j])
                {
                    if (f[i-1][k]+1 > f[i][j])
                    {
                        f[i][j] = f[i-1][k]+1;
                        for (int p=1; p<=f[i-1][k]; p++)
                            lcis[j][p] = lcis[k][p];
                        lcis[j][f[i][j]] = B[j];
                    }
                }
        }
        else f[i][j] = f[i-1][j];
    }
}

for(int p=1;p<=f[N][ansj];p++)
    printf("%d ",lcis[ansj][p]);
puts("");

方法2

设 path[i][j] 是 f[i][j] 转移时的路径。这样就将 path[i][j] 与 A[1..i] 和 B[1..j] 联系起来.

每次随着 f[i][j] 的转移记录 path[i][j].

\begin{cases}k && (A[i]=B[j])\\ j && (A[i]\not=B[j])\end{cases}

输出的递归函数应有两个参数， Output(i,j) 沿着 f[i][j] 转移时的路径递归到 Output(i-1,path[i][j]) ，并在 path[i][j] \not= j 时输出 B[j] 。

若 path[i][j] = j ,则说明这里是没有增加 LCIS 长度的转移，此时应该继续递归而不输出。

这种方法的时间复杂度为 O(n^3).

核心代码2

for (int i=1; i<=N; i++)
{
    for (int j=1; j<=M; j++)
    {
        if (A[i] == B[j])
        {
            for (int k=1; k<j; k++)
                if (B[k]<B[j])
                    if (f[i-1][k]+1 > f[i][j])
                    {
                        f[i][j] = f[i-1][k]+1;
                        path[i][j] = k;
                    }
        }
        else
        {
            f[i][j] = f[i-1][j];
            path[i][j] = j;
        }
    }
}

void Output(int i,int j)
{
    if(i==0) return;
    Output(i-1,path[i][j]);
    if (path[i][j] != j)
        printf("%d ",B[j]);
    return;
}

if(f[N][ansj])
{
    Output(N,ansj);
    puts("");
}

【优化】

注意到在 B[j]=A[i] 时的转移决策集合中有 1\leq k<j 的形式，并且其决策单调，具体到这里就是被排除的决策不会再进入决策集合中

也就是决策集合 \{k\} 实际上可以在 j 的循环中用一个变量以储存最优值的方式维护一下.

每次 j++ 时，决策集合 \{k\} 中会新增一个元素 k=j-1,

该决策合法的条件是 B[k]<B[j],B[j]=A[i]

虽然随着 j 的增加， B[j]会变化,也许会使 \{k\} 中的一些元素退出决策集合.

但是,只有 B[j]=A[i] 时决策才需要用到这个决策集合 \{k\} 。

因为枚举 j 时 A[i] 不变,所以,我们保持原有的元素不变，

当 B[j-1]<A[i] 时,用新的决策 k=j-1 来更新原决策集合中的最优决策.

即 if (B[j]<A[i] && f[i-1][j]>f[i-1][k]) k=j;

这样就可以不用在 j 的循环中再写 k 的循环寻找最优决策了

优化后两种方法的时间复杂度都降了一维，时间复杂度为 O(n^2).

【总结】

状态转移时,应注意决策集合的范围变化,设计出相应的维护方式,如用单一变量记录最优值或用线段树、单调队列等数据结构优化.
记录路径的数组应与答案数组的维度相同,且记录的信息应为抽象的转移路径,而不是"上一个数"等较直观的信息,否则容易被覆盖出错.

最后献上AC代码两份

方法1

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=5005;
int N, M, A[MAXN], B[MAXN];
int f[MAXN][MAXN], ansj=0, lcis[MAXN][MAXN];
void LCIS();
void Input();
int main()
{
    Input();
    LCIS();
    printf("%d\n",f[N][ansj]);
    for (int p=1; p<=f[N][ansj]; p++)
        printf("%d ",lcis[ansj][p]);
    puts("");
    return 0;
}
void LCIS()
{
    memset (f, 0, sizeof(f));
    memset (lcis, 0, sizeof(lcis));
    for (int i=1; i<=N; i++)
    {
        for (int j=1,k=0; j<=M; j++)
        {
            if (A[i] == B[j])
            {
                f[i][j] = f[i-1][k]+1;
                for (int p=1; p<=f[i-1][k]; p++)
                    lcis[j][p] = lcis[k][p];
                lcis[j][f[i][j]] = A[i];
            }
            else f[i][j] = f[i-1][j];
            if (B[j]<A[i] && f[i][j]>f[i][k])
                k = j;
        }
    }
    for (int i=1; i<=M; i++)
        if (f[N][i] > f[N][ansj])
            ansj = i;
    return;
}
void Input()
{
    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]);
    return;
}

方法2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=5005;
int N, M, A[MAXN], B[MAXN];
int f[MAXN][MAXN], path[MAXN][MAXN], ansj=0;
void LCIS();
void Input();
void Output(int,int);
int main()
{
    Input();
    LCIS();
    printf("%d\n", f[N][ansj]);
    if (f[N][ansj])
    {
        Output(N,ansj);
        puts("");
    }
    return 0;
}
void LCIS()
{
    memset (f, 0, sizeof(f));
    memset (path, 0, sizeof(path));
    for (int i=1; i<=N; i++)
    {
        for (int j=1,k=0; j<=M; j++)
        {
            if (A[i] == B[j])
            {
                f[i][j] = f[i-1][k]+1;
                path[i][j] = k;
            }
            else
            {
                f[i][j] = f[i-1][j];
                path[i][j] = j;
            }
            if(B[j]<A[i] && f[i][j]>f[i][k])
                k = j;
        }
    }
    for(int i=1; i<=M; i++)
        if(f[N][i] > f[N][ansj])
            ansj = i;
    return;
}
void Output(int i,int j)
{
    if(i==0) return;
    Output(i-1,path[i][j]);
    if (path[i][j] != j)
        printf("%d ",B[j]);
    return;
}
void Input()
{
    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]);
    return;
}

附：我在尝试只用一维数组存路径时被Hack掉的数据

Input：

100
9060 2520 8100 4950 4950 6020 2360 2230 7100 7100 2360 8100 2520 2520 9060 2520 9065 2520 8100 9065 9065 2520 9065 4950 2520 9490 6020 2520 8100 2520 3400 1934 7100 9060 8100 2520 3400 1934 3400 1934 9490 9184 2230 2520 2360 9065 7100 2230 2520 2360 9065 2520 7100 1934 8100 2520 6020 5650 2520 5650 5650 9490 5650 1934 4950 4360 9060 6020 9184 2520 4950 9060 8100 1934 9184 2360 4950 6020 4360 7100 2360 8100 1934 9060 2520 3400 3400 4360 1934 8100 1934 2520 4360 5650 4360 6020 1934 2230 9065 2520
100
4950 8100 7100 9065 9060 7100 7100 6020 4950 2360 9184 2230 5650 4360 4950 5650 6020 7100 3400 7100 4360 9065 2230 2520 9065 3400 2360 3400 9490 4360 2230 4360 2520 8100 8100 2360 2230 8100 6020 5650 2230 4950 3400 3400 2360 4360 9065 9490 1934 2230 9060 5650 7100 2520 3400 2360 7100 2230 5650 8100 9184 9065 1934 7100 8100 1934 8100 2230 2230 7100 4950 5650 3400 5650 2360 2230 9065 9490 1934 9060 1934 5650 9184 9184 8100 6020 5650 1934 2230 4360 4360 2230 8100 4950 1934 2360 9060 2360 2230 4950

Output：

9
2230 2360 2520 3400 4360 4950 6020 8100 9060