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

文章封面

1

一、题目解读

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

二、解题步骤

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

2.读取输入数字序列

3.初始化dp数组(大小为10,对应0-9的数字)

4.遍历数字序列:

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

更新dp[末位]的值

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

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)题解:动态规划与数字首尾匹配的完美应用 算法竞赛必备技巧

评论

暂无评论