AcWing 4958. 接龙数列

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4958. 接龙数列原题链接中等

作者：

k_irito , 2025-04-01 22:06:23 ·江苏 , 所有人可见 , 阅读 1

1

1

暴力动态规划

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
string s;
int l[N], r[N]; // 存储每个数字的首位和末位
int g[N], f[10]; // g[i]表示以第i个数结尾的最长序列长度

int main()
{
    scanf("%d", &n);

    // 预处理所有数字的首尾
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        l[i] = s[0] - '0', r[i] = s.back() - '0';
    }

    int res = 0;
    // 双重循环LIS变种
    for (int i = 1; i <= n; i ++)
    {
        g[i] = 1; // 初始长度为1
        for (int j = 1; j < i; j ++) // 检查前面所有数字
        {
            if (l[i] == r[j]) // 满足接龙条件
                g[i] = max(g[i], g[j] + 1);
        }
        res = max(res, g[i]); // 维护全局最大值
    }

    printf("%d", n - res);

    return 0;
}

特点与优劣

算法：暴力动态规划（LIS变种）
时间复杂度： $O(n^2)$
空间复杂度： $O(n)$
优点：
- 逻辑直观，易于理解
- 不需要额外空间优化
缺点：
- 无法处理 $n>10^4$ 的数据规模
- 存在大量重复计算

空间优化动态规划

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
string s;
int l[N], r[N]; // 存储每个数字的首尾
int g[N], f[10]; // f[r]记录以数字r结尾的最大长度

int main()
{
    scanf("%d", &n);

    // 预处理首尾数字
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        l[i] = s[0] - '0', r[i] = s.back() - '0';
    }

    int res = 0;
    // 优化后的动态规划
    for (int i = 1; i <= n; i ++)
    {
        g[i] = max(1, f[l[i]] + 1); // 接在相同首数字的序列后
        f[r[i]] = max(f[r[i]], g[i]); // 更新末位数字的最大长度
        res = max(res, g[i]); // 维护全局最大值
    }

    printf("%d", n - res);

    return 0;
}

特点与优劣

算法：空间优化动态规划
时间复杂度： $O(n)$
空间复杂度： $O(n)$
优点：
- 利用数字0-9的有限性优化
- 可处理 $n≤10^5$ 规模
缺点：
仍保留了不必要的g[]数组
预处理阶段需要额外空间

极致优化的动态规划

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
string s;
int g, f[10]; // f[r]实时维护以r结尾的最大长度

int main()
{
    scanf("%d", &n);

    int res = 0;
    // 极简动态规划实现
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        int l = s[0] - '0', r = s.back() - '0';

        g = max(1, f[l] + 1); // 当前数字能形成的序列长度
        f[r] = max(f[r], g);  // 更新末位数字记录
        res = max(res, g);    // 维护全局最大值
    }

    printf("%d", n - res);

    return 0;
}

特点与优劣

算法：极致优化的动态规划
时间复杂度： $O(n)$
空间复杂度： $O(1)$ （仅用常数空间）
优点：
- 空间效率最优
- 实时处理，无需预处理
- 可处理 $n≤10^7$ 规模
缺点：
丢失了每个数字的具体序列信息
代码逻辑需要更深入理解

核心算法

动态规划：使用f[r]数组记录以数字r结尾的最长接龙序列长度
状态转移：对于每个数字，其能形成的接龙序列长度 = 以其首数字结尾的序列长度 + 1
贪心更新：始终维护以每个数字结尾的最长序列长度

分析过程

问题转化：最少删除数 = 总数 - 最长接龙序列长度
关键观察：
- 每个数字只需关注其首尾数字
- 序列连续性仅取决于前一个数的末位与当前数的首位
状态设计：
- f[r]表示当前以数字r结尾的最长序列长度
- 对于数字s，其贡献是使以s.back()结尾的序列可能变长

结论

最终解：n - max(f[0..9])
算法正确性：通过动态维护以各数字结尾的最长序列，确保找到全局最优解
关键优化：将O(n²)的LIS问题转化为O(n)的特定条件DP

时间复杂度

$T(n) = O(n \cdot k) \quad \text{其中} \ k=10 \ \text{为常数} \\ \Rightarrow T(n) = O(n)$

注意事项：字符串处理操作s.back()在实际实现中为O(1)

应用场景

序列优化问题：需要保持特定顺序关系的序列处理
数据清洗：识别符合特定规则的数据子集
文本处理：首尾字符匹配的相关应用
推荐系统：构建满足转移条件的内容链

典型特征：当问题可以转化为”首尾相连”的链式结构时适用

三者的区别与对比

特性	代码1	代码2	代码3
算法	暴力DP	优化DP	极致优化DP
时间	$O(n^2)$	$O(n)$	$O(n)$
空间	$O(n)$	$O(n)$	$O(1)$
预处理	需要	需要	不需要
适用规模	$n≤10^3$	$n≤10^5$	$n≤10^7$
可读性	★★★★★	★★★★	★★★