侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-04-13 / 0 评论 / 0 点赞 / 164 阅读 / 1,156 字
温馨提示:
本文最后更新于 2023-04-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4958. 接龙数列 - AcWing题库


对于一个长度为 KK 的整数数列: A1,A2,...,AKA_1, A_2, . . . , A_K ,我们称之为接龙数列当且仅当 AiA_i 的首位数字恰好等于 Ai1A_{i−1} 的末位数字 ( 2iK2 ≤ i ≤ K )。

例如 12,23,35,56,61,1112, 23, 35, 56, 61, 11 是接龙数列; 12,23,34,5612, 23, 34, 56 不是接龙数列,因为 5656 的首位数字不等于 3434 的末位数字。

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

现在给定一个长度为 NN 的数列 A1,A2,...,ANA_1, A_2, . . . , A_N ,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?

输入格式

第一行包含一个整数 NN

第二行包含 NN 个整数 A1,A2,...,ANA_1, A_2, . . . , A_N

输出格式

一个整数代表答案。

数据范围

对于 20%20\% 的数据, 1N201 ≤ N ≤ 20
对于 50%50\% 的数据, 1N100001 ≤ N ≤ 10000
对于 100%100\% 的数据, 1N1051 ≤ N ≤ 10^51Ai1091 ≤ A_i ≤ 10^9 。所有 AiA_i 保证不包含前导 00

输入样例:

5
11 121 22 12 2023

输出样例:

1

样例解释

删除 2222 ,剩余 11,121,12,202311, 121, 12, 2023 是接龙数列。

解题

方法一:动态规划

思路

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

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

动态规划:

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

这样做的时间复杂度是 O(n2)O(n^2) ,只能过前 50%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(n2)O(n^2)

优化

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

这样做可以优化掉内层循环,时间复杂度降为 O(n)O(n) ,可以过全部 100%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)O(n)

0

评论区