【线性DP】接龙数列【十四届蓝桥杯省赛CB】

题目

4958. 接龙数列 - AcWing题库

---

对于一个长度为 $K$ 的整数数列： $A_1, A_2, . . . , A_K$ ，我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i−1}$ 的末位数字 ( $2 ≤ i ≤ K$ )。

例如 $12, 23, 35, 56, 61, 11$ 是接龙数列； $12, 23, 34, 56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。

所有长度为 $1$ 的整数数列都是接龙数列。

现在给定一个长度为 $N$ 的数列 $A_1, A_2, . . . , A_N$ ，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数 $A_1, A_2, . . . , A_N$ 。

输出格式

一个整数代表答案。

数据范围

对于 $20\%$ 的数据， $1 ≤ N ≤ 20$ 。
对于 $50\%$ 的数据， $1 ≤ N ≤ 10000$ 。
对于 $100\%$ 的数据， $1 ≤ N ≤ 10^5$ ， $1 ≤ A_i ≤ 10^9$ 。所有 $A_i$ 保证不包含前导 $0$ 。

输入样例：

5
11 121 22 12 2023

输出样例：

1

样例解释

删除 $22$ ，剩余 $11, 121, 12, 2023$ 是接龙数列。

解题

方法一：动态规划

思路

把问题「最少从中删除多少个数，可以使剩下的序列是接龙序列」转换为「找出序列中的最长接龙子序列」，再拿序列总长度减去最长接龙子序列即得到最少要删除的数。

找最长xx子序列不免会想到 LIS问题 ，事实上把动态转移的条件改一下就可以用在该题上了，如下：

动态规划：

• 状态定义： $f[i]$ 表示所有以数组中第 $i$ 个数结尾的接龙子序列的最大长度；
• 状态转移：当 $A_j$ 的末尾数字等于 $A_i$ 的首位数字时， $f[i] = \max(f[i], f[j] + 1), \enspace j = 1 \dots i -1$ ；
• 初始状态： $f[0 \dots n - 1] = 1$ 。

这样做的时间复杂度是 $O(n^2)$ ，只能过前 $50\%$ 的数据，还需要下面介绍的优化。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, a[N], f[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        int h = a[i];
        while (h / 10) h /= 10;
        for (int j = 0; j < i; ++j) {
            if (a[j] % 10 == h) f[i] = max(f[i], f[j] + 1);
        }
    }
    int mx = 0;
    for (int i = 0; i < n; ++i) mx = max(mx, f[i]);
    printf("%d\n", n - mx);

    return 0;
}

时间复杂度：$O(n^2)$ 。

优化

发现相较于 $LIS$ 可以以任意在数组中的数结尾来说，接龙序列只会以 $0\dots 9$ 结尾，于是可以维护一个长度为 $10$ 的数组 $g$ ，$g[d]$ 表示以数字 $d$ 结尾的最长接龙子序列的长度，这样以来， $f[i]$ 就可以用 $g[head(A_i)]$ 进行状态转移，同时 $g[tail(A_i)]$ 也可以用 $f[i]$ 来反向更新。

这样做可以优化掉内层循环，时间复杂度降为 $O(n)$ ，可以过全部 $100\%$ 的数据了。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, a[N], f[N], g[10];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        int h = a[i], t = a[i] % 10;
        while (h / 10) h /= 10;
        f[i] = g[h] + 1;
        g[t] = max(g[t], f[i]);
    }
    int mx = 0;
    
    for (int i = 0; i < n; ++i) mx = max(mx, f[i]);
    printf("%d\n", n - mx);

    return 0;
}

时间复杂度：$O(n)$ 。