E.接龙数列【蓝桥杯】/动态规划
接龙数列
题目描述
对于一个长度为 K 的整数数列:A1, A2, . . . , AK,我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列;12, 23, 34, 56 不是接龙数列,因为 56的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1, A2, . . . , AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, . . . , AN。
输出格式
一个整数代表答案。
样例输入
5
11 121 22 12 2023
样例输出
1
提示
删除 22,剩余 11, 121, 12, 2023 是接龙数列。
对于 20% 的数据,1 ≤ N ≤ 20。
对于 50% 的数据,1 ≤ N ≤ 10000。
对于 100% 的数据,1 ≤ N ≤ 105,1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。
动态规划
dp[i]表示以i为数字最后一位的最长接龙数列长度
x是该数最高位,y表示最低位
转移方程dp[y]=max(dp[x]+1,dp[y]);,dp[x]+1表示选择当前数,dp[y]表示不选择当前数
#include<iostream>
#include<cstring>
using namespace std;
int main()
{int dp[15]={0};int n,m=1;cin>>n;for(int i=0;i<n;i++){string s;cin>>s;int x=s[0]-'0',y=s[s.size()-1]-'0';dp[y]=max(dp[x]+1,dp[y]);m=max(m,dp[y]);}cout<<n-m<<endl;return 0;
}
相关文章:
E.接龙数列【蓝桥杯】/动态规划
接龙数列 题目描述 对于一个长度为 K 的整数数列:A1, A2, . . . , AK,我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。 例如 12, 23, 35, 56, 61, 11 是接龙数列;12, 23, 34, 56 不是接龙数列…...
cv2.cvtColor()将二维转化为彩色图像
我们如果要将一维的图像转化为三维的彩色图像 import cv2 img cv2.cvtColor(img.squeeze(0), cv2.COLOR_GRAY2BGR) 这里的img.squeeze为二维数据,img为三维数据,所以压缩掉一个维度 。这样就将图像转化为了三维彩色图像。 cv2.imshow(Image, img) c…...
为什么 VSCode 不用 Qt 而要用 Electron?
为什么 VSCode 不用 Qt 而要用 Electron? 在开始前我有一些资料,是我根据网友给的问题精心整理了一份「Qt 的资料从专业入门到高级教程」, 点个关注在评论区回复“888”之后私信回复“888”,全部无偿共享给大家!!&am…...
环信ChatroomUIKit功能详解——超详细介绍
聊天室是当下泛娱乐社交应用中最经典的玩法,通过调用环信的 IM SDK 接口,可以快速创建聊天室。如果想根据自己业务需求对聊天室应用的 UI界面、弹幕消息、礼物打赏系统等进行自定义设计,最高效的方式则是使用环信的 ChatroomUIKit 。 文档地址…...
怎么读取springboot中的properties.yml配置文件里的配置值(亲测有效)
怎么读取springboot中的properties.yml配置文件里的配置值 test:username: name主配置类中加上 EnableConfigurationProperties(MailConfigProperties.class)类上加ConfigurationPropetise("test“),属性就会自动注入配置值; ConfigurationPropetise("…...
18、设计模式之解释器模式(Interpreter)
一、什么是解释器模式 解释器模式是一种行为型设计模式。解释器模式就像是一种自定义语言,我们可以定义该语言的语法规则,然后从中解析出具体的命令或表达式,最终执行相应的操作。 eg:这种模式比较冷门,不怎么使用。 …...
cpp qt 一个奇怪的bug
今天在用cpp qt的时候发现了一个奇怪的东西 这是我的源代码 #include "mywidget.h" #include <QPushButton>myWidget::myWidget(QWidget *parent): QWidget(parent) {QPushButton * btn1 new QPushButton;btn1->show();btn1->setParent(this);btn1-&g…...
第6章:MATLAB文本数据处理进阶篇的目录 (MATLAB入门课程)
讲解视频:可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。 MATLAB教程新手入门篇(数学建模清风主讲,适合零基础同学观看)_哔哩哔哩_bilibili 第6章:MATLAB文本数据处理进阶篇 6.1 文本格式化 …...
软件杯 深度学习 opencv python 公式识别(图像识别 机器视觉)
文章目录 0 前言1 课题说明2 效果展示3 具体实现4 关键代码实现5 算法综合效果6 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 基于深度学习的数学公式识别算法实现 该项目较为新颖,适合作为竞赛课题方向,学…...
vscode通过多个跳板机连接目标机(两种方案亲测成功)
1、ProxyJump(推荐使用) 需要OpenSSH 7.3以上版本才可使用,可用下列命令查看: ssh -V ProxyJump命令行使用方法 ssh -J [email protected]:port1,[email protected]:port2 一层跳板机: ssh dst_usernamedst_ip -…...
C++基础复习003
vector去重 第一种,利用set容器的特性进行去重: #include <iostream> #include <vector> #include <set> using namespace std; int main() {vector<int>test{1,2,3,3,3,4,2,3,5,2,63,56,34,24};set<int>s(test.begin(),…...
Docker Commit提交
Docker Commit提交 Docker Commit镜像提交 以一个正在运行的tomcat为例因为docker拉取的镜像都是删减版,所以需要将webapp.dist的文件内容复制到webapps中再将自己制作的镜像放在正在运行服务器上,不是云端服务器上 #进入tomcat,这是一个正…...
百度现在应该怎么去做搜索SEO优化?(川圣SEO)蜘蛛池
baidu搜索:如何联系八爪鱼SEO? baidu搜索:如何联系八爪鱼SEO? baidu搜索:如何联系八爪鱼SEO? 百度搜索引擎优化(SEO)是一种通过优化网站,提升网页在百度搜索结果中的排…...
登录凭证------
为什么需要登录凭证? web开发中,我们使用的协议http是无状态协议,http每次请求都是一个单独的请求,和之前的请求没有关系,服务器就不知道上一步你做了什么操作,我们需要一个办法证明我没登录过 制作登录凭…...
matplotlib系统学习记录
日期:2024.03.12 内容:将matplotlib的常用方法做一个记录,方便后续查找。 基本使用 # demo01 from matplotlib import pyplot as plt # 设置图片大小,也就是画布大小 fig plt.figure(figsize(20,8),dpi80)#图片大小,清晰度# 准…...
【DL】ML系统学习笔记 1
【DL】ML系统学习笔记 1 1. 机器学习定义2. 机器学习三大任务3. 机器学习定义回归举例4. Gradient Descent 优化5. Gradient Descent 优化步骤6. 回归步骤小姐7. Linear models8. 核心步骤流程9. 模型优化9. 深度学习引出1. 机器学习定义 Machine Learning Looking for Functio…...
ffmpeg视频处理常用命令
1.ffmpeg主要参数 -f fmt(输入/输出) 强制输入或输出文件格式。 格式通常是自动检测输入文件, 并从输出文件的文件扩展名中猜测出来,所以在大多数情况下这个选项是不需要的。-i url(输入) 输入文件的网址-…...
前端npm和yarn更换国内淘宝镜像
NPM 查询当前镜像 npm get registry 设置为淘宝镜像 npm config set registry https://registry.npm.taobao.org/ (旧地址) npm config set registry https://registry.npmmirror.com/ (最新地址) 设置为官方镜像 npm config set registry https://registry.n…...
华为配置OSPF的Stub区域示例
配置OSPF的Stub区域示例 组网图形 图1 配置OSPF Stub区域组网图 Stub区域简介配置注意事项组网需求配置思路操作步骤配置文件 Stub区域简介 Stub区域的ABR不传播它们接收到的自治系统外部路由,在Stub区域中路由器的路由表规模以及路由信息传递的数量都会大大减少…...
学会Web UI框架--Bootstrap,快速搭建出漂亮的前端界面
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 所属的专栏:前端泛海 景天的主页:景天科技苑 文章目录 Bootstrap1.Bootstrap介绍2.简单使用3.布局容器4.Bootstrap实现轮播…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
