蓝桥杯2023接龙数列（洛谷P9242）题解：动态规划与数字首尾匹配的完美应用 算法竞赛必备技巧

一、题目解读

这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列（每个数字的首位等于前一个数字的末位），并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力，是理解数字特征处理和状态转移的典型案例。

二、解题思路

1. 1.预处理数字的首位和末位

2. 2.使用动态规划数组记录以每个数字结尾的最长序列长度

3. 3.状态转移方程：dp[末位] = max(dp[末位], dp[首位]+1)

4. 4.最终结果为总长度减去最长序列长度

三、解题步骤

1. 1.处理n=1的特殊边界情况

2. 2.读取输入数字序列

3. 3.初始化dp数组（大小为10，对应0-9的数字）

4. 4.遍历数字序列：

• 获取当前数字的首位和末位

• 更新dp[末位]的值

5. 5.找出dp数组中的最大值

6. 6.计算并输出需要删除的数字个数

四、代码实现（带注释）

#include<iostream>
#include<string>
#include<vector>
using namespace std;

// 获取数字首位
int head(int n){
    return (to_string(n))[0]-'0';
}

// 获取数字末位
int tail(int n){
    return n%10;
}

// 核心计算函数
int aaa(int a[],int n){
    int dp[10]={0};  // dp数组，索引表示数字末位
    int ret=0;
    for(int i=0;i<n;i++){
        dp[tail(a[i])]=max(dp[tail(a[i])],dp[head(a[i])]+1);
    }
    for(int i=0;i<10;i++){
        ret=max(dp[i],ret);  // 找出最长序列
    }
    return n-ret;  // 计算需要删除的数字个数
}

int main(){
    int n;
    cin>>n;
    if(n==1){  // 特殊情况处理
        cout<<0;
        return 0;
    }
    int a[100005];
    for(int i=0;i<n;i++){
        cin>>a[i];  // 读取输入
    }
    cout<<aaa(a,n);
    return 0;
}

这段代码展示了如何用动态规划高效解决接龙数列问题，时间复杂度O(n)，空间复杂度O(1)。

六、总结
本题展示了动态规划在数字序列处理中的高效应用，通过维护以各数字结尾的最长序列长度，巧妙地解决了接龙问题。这种基于数字特征的动态规划思路，可以扩展到其他序列处理问题，是算法竞赛中的必备技巧。