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

贾蔷
• 阅读 98

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

一、题目解读

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

二、解题步骤

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

点赞
收藏
评论区
推荐文章
贾蔷 贾蔷
3星期前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
深度学习 深度学习
3星期前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
深度学习 深度学习
3星期前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
贾蔷 贾蔷
3星期前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
贾蔷 贾蔷
3星期前
洛谷P1168题终极解析:双堆法高效计算动态中位数 | 数据结构实战教程
一、问题理解与算法思路题目要求我们动态维护一个序列,并在每次读取奇数个数字时输出当前序列的中位数。这道题考察了两个核心算法点:堆数据结构的应用和中位数的高效计算。我们采用双堆法(一个大根堆和一个小根堆)来高效解决这个问题。‌解题关键步骤‌:使用大根堆存储较
深度学习 深度学习
3星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
3星期前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
贾蔷 贾蔷
3星期前
【2023 CSP-S密码锁(洛谷P9752)】题解:动态规划与集合交集的巧妙应用
一、题目解读2023年CSPS的“密码锁”题目(洛谷P9752)要求破解一种环形密码锁机制。题目给定n组状态,每个状态由5个数字组成,通过“单拨圈”或“双相邻拨圈”操作可改变数字。正确密码需满足:通过操作能从初始状态转换到所有给定状态,且给定状态本身不能作
深度学习 深度学习
1星期前
NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解
一、题目解读问题(,)要求使用给定数量的火柴棒,构造形如ABC的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式数量。题目核心在于将数字拆解与火柴棒消耗建模为数学问题,寻找高效解法。二、解题思路采用火柴棒计数策略:1.关系
贾蔷 贾蔷
6天前
【动态规划入门】力扣509题:斐波那契数列的经典解法与优化思路
一、题目解读‌是一个经典的数学问题,在计算机科学中常被用作教学的入门案例。这个神奇的数列从0和1开始,后续每个数字都是前两个数字之和。题目要求我们计算第n个,看似简单的问题背后却蕴含着重要的算法思想。当n较小时,这个问题似乎微不足道,但随着n的增大,不同的