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实现轮播…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
