当前位置: 首页 > news >正文

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 的整数数列&#xff1a;A1, A2, . . . , AK&#xff0c;我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。 例如 12, 23, 35, 56, 61, 11 是接龙数列&#xff1b;12, 23, 34, 56 不是接龙数列&#xf…...

cv2.cvtColor()将二维转化为彩色图像

我们如果要将一维的图像转化为三维的彩色图像 import cv2 img cv2.cvtColor(img.squeeze(0), cv2.COLOR_GRAY2BGR) 这里的img.squeeze为二维数据&#xff0c;img为三维数据&#xff0c;所以压缩掉一个维度 。这样就将图像转化为了三维彩色图像。 cv2.imshow(Image, img) c…...

为什么 VSCode 不用 Qt 而要用 Electron?

为什么 VSCode 不用 Qt 而要用 Electron? 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「Qt 的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&am…...

环信ChatroomUIKit功能详解——超详细介绍

聊天室是当下泛娱乐社交应用中最经典的玩法&#xff0c;通过调用环信的 IM SDK 接口&#xff0c;可以快速创建聊天室。如果想根据自己业务需求对聊天室应用的 UI界面、弹幕消息、礼物打赏系统等进行自定义设计&#xff0c;最高效的方式则是使用环信的 ChatroomUIKit 。 文档地址…...

怎么读取springboot中的properties.yml配置文件里的配置值(亲测有效)

怎么读取springboot中的properties.yml配置文件里的配置值 test:username: name主配置类中加上 EnableConfigurationProperties(MailConfigProperties.class)类上加ConfigurationPropetise("test“),属性就会自动注入配置值&#xff1b; ConfigurationPropetise("…...

18、设计模式之解释器模式(Interpreter)

一、什么是解释器模式 解释器模式是一种行为型设计模式。解释器模式就像是一种自定义语言&#xff0c;我们可以定义该语言的语法规则&#xff0c;然后从中解析出具体的命令或表达式&#xff0c;最终执行相应的操作。 eg&#xff1a;这种模式比较冷门&#xff0c;不怎么使用。 …...

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入门课程)

讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 第6章&#xff1a;MATLAB文本数据处理进阶篇 6.1 文本格式化 …...

软件杯 深度学习 opencv python 公式识别(图像识别 机器视觉)

文章目录 0 前言1 课题说明2 效果展示3 具体实现4 关键代码实现5 算法综合效果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于深度学习的数学公式识别算法实现 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学…...

vscode通过多个跳板机连接目标机(两种方案亲测成功)

1、ProxyJump&#xff08;推荐使用&#xff09; 需要OpenSSH 7.3以上版本才可使用&#xff0c;可用下列命令查看&#xff1a; ssh -V ProxyJump命令行使用方法 ssh -J [email protected]:port1,[email protected]:port2 一层跳板机&#xff1a; ssh dst_usernamedst_ip -…...

C++基础复习003

vector去重 第一种&#xff0c;利用set容器的特性进行去重&#xff1a; #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拉取的镜像都是删减版&#xff0c;所以需要将webapp.dist的文件内容复制到webapps中再将自己制作的镜像放在正在运行服务器上&#xff0c;不是云端服务器上 #进入tomcat&#xff0c;这是一个正…...

百度现在应该怎么去做搜索SEO优化?(川圣SEO)蜘蛛池

baidu搜索&#xff1a;如何联系八爪鱼SEO&#xff1f; baidu搜索&#xff1a;如何联系八爪鱼SEO&#xff1f; baidu搜索&#xff1a;如何联系八爪鱼SEO&#xff1f; 百度搜索引擎优化&#xff08;SEO&#xff09;是一种通过优化网站&#xff0c;提升网页在百度搜索结果中的排…...

登录凭证------

为什么需要登录凭证&#xff1f; web开发中&#xff0c;我们使用的协议http是无状态协议&#xff0c;http每次请求都是一个单独的请求&#xff0c;和之前的请求没有关系&#xff0c;服务器就不知道上一步你做了什么操作&#xff0c;我们需要一个办法证明我没登录过 制作登录凭…...

matplotlib系统学习记录

日期&#xff1a;2024.03.12 内容&#xff1a;将matplotlib的常用方法做一个记录&#xff0c;方便后续查找。 基本使用 # demo01 from matplotlib import pyplot as plt # 设置图片大小,也就是画布大小 fig plt.figure(figsize(20,8),dpi80)#图片大小&#xff0c;清晰度# 准…...

【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&#xff08;输入/输出&#xff09; 强制输入或输出文件格式。 格式通常是自动检测输入文件&#xff0c; 并从输出文件的文件扩展名中猜测出来&#xff0c;所以在大多数情况下这个选项是不需要的。-i url&#xff08;输入&#xff09; 输入文件的网址-…...

前端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不传播它们接收到的自治系统外部路由&#xff0c;在Stub区域中路由器的路由表规模以及路由信息传递的数量都会大大减少…...

学会Web UI框架--Bootstrap,快速搭建出漂亮的前端界面

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属的专栏&#xff1a;前端泛海 景天的主页&#xff1a;景天科技苑 文章目录 Bootstrap1.Bootstrap介绍2.简单使用3.布局容器4.Bootstrap实现轮播…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...