蓝桥杯2023接龙数列（洛谷P9242）题解：动态规划与数字首尾匹配的完美应用

一、题目解读

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

二、解题步骤

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;
}

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