【C++算法入门】动态规划—调手表问题
距离蓝桥杯还有32天。昨天在蓝桥杯官网刷到一个较为简单的动态规划入门题发现此前已经做过了而当时只通过了一半的测验数据。昨天重写了这个题目改变了一下思路竟全部通过了。一、原题复现M78星云的手表• 一圈有 n 分钟0~n-1• 两个按钮1和k1. 1当前数字 1超过 n 就回到 02. k当前数字 k超过n就回到0问从 0 出发调到 每一个数字 最少要按多少次这些最少次数里 最大的那个 是多少二、思路分析记得这是我刚刷题没多久写的代码显然虽然能成功编译但求min的函数出现了思路的问题且想法单一对一小时内的分钟进行循环每个循环求出能调到当前分钟的最优解。如果在竞赛场上没有其他思路我们确实可以考虑单一或者题目所举样例的情况尽可能保证拿分。现在我们来分析这道题既然从时间出发较为复杂我们不妨从次数入手来不断优化到每个时间的次数。比如n5k3。dp[0]我们赋值为0那么dp[1]1,dp[3]1继续dp[2]2,dp[4]2dp[4]2,dp[1]2。此时我们可以发现到时间1的路径有两条及01和033。这里就体现了优化的过程用一个公式表达就是1(33)%5;dp[1]min(dp[1],dp[3]1)。想到这里思路是否就明了了呢但是大家想来可能会和我一开始一样不知道要循环几次n好像不行接下来我便在代码中融入我的思考。下面我就用代码对它进行实现代码中也包含了我的注解。各位可以适当参考一下。我们可以用上面举过的例子对其进行过程分析n5k3。dp[0]0第一轮的情况dp[1]1,dp[3]1,将其都进队;第二轮以dp[1]作为基准值dp[2]2,dp[4]2,将其都进队;第三轮以dp[3]作为基准值dp[4]2,dp[1]2。此时可以看到我们得到的dp[1]1,小于我们原来得到的dp[1]故其不进队dp[4]同理。我们利用队列的本质便是用队里的元素去更新外界元素找到最小值试想如果将dp[1]赋值给2并进队那么接下来得到的路径是不是要比dp[1]1时都要大所以不能进队。所以也很容易想到当队列为空所有路径都走完了且找不到更加小的值了达到了优化的目标。以上是我关于蓝桥杯中调手表问题的所有思考了欢迎讨论。

相关新闻

蓄电池与超级电容混合储能系统的功率分配与能量管理Simulink仿真研究

蓄电池与超级电容混合储能系统的功率分配与能量管理Simulink仿真研究

蓄电池与超级电容混合储能并网matlab/simulink仿真模型。 (1)混合储能采用低通滤波器进行功率分配,可有效抑制功率波动,并对超级电容的soc进行能量管理,soc较高时多放电,较低时少放电,soc较低时…

2026/7/4 8:59:06 阅读更多 →
编的是C++程序,用的却是Python turtle的命令!青少年学C++精灵库可以用于做什么?

编的是C++程序,用的却是Python turtle的命令!青少年学C++精灵库可以用于做什么?

一、传统方向(牛娃必备):用于打信奥......。 二、新的方向(普娃宝典):创造与探索,从兴趣走向专业。 绘图启蒙,跨界融合 编的是C程序,用的却是Python turtle的命令&#…

2026/7/4 1:03:43 阅读更多 →
win10右键用**软件打开(用vsccode打开文件夹)怎么做

win10右键用**软件打开(用vsccode打开文件夹)怎么做

1.winr输入regedit回车2.找到目录“计算机\HKEY_CLASSES_ROOT\Directory\shell”3.新建一个项命名为“open with ***”(你要打开的软件)3.在这个目录下新建一个项命名为“command”4.修改“默认”值为"要打开的软件地址"空格"%V"我的…

2026/5/17 11:58:32 阅读更多 →

最新新闻

HPL1Engine场景管理指南:高效加载与渲染3D世界的10个技巧

HPL1Engine场景管理指南:高效加载与渲染3D世界的10个技巧

HPL1Engine场景管理指南:高效加载与渲染3D世界的10个技巧 【免费下载链接】HPL1Engine A real time 3D engine. 项目地址: https://gitcode.com/gh_mirrors/hp/HPL1Engine HPL1Engine是一款功能强大的实时3D引擎,为游戏开发者提供了创建沉浸式3D世…

2026/7/4 8:57:26 阅读更多 →
Elm-platform安装教程:Windows、macOS、Linux三大平台详细步骤

Elm-platform安装教程:Windows、macOS、Linux三大平台详细步骤

Elm-platform安装教程:Windows、macOS、Linux三大平台详细步骤 【免费下载链接】elm-platform Bundle of all core development tools for Elm 项目地址: https://gitcode.com/gh_mirrors/el/elm-platform 想要开始 Elm 编程之旅吗?Elm-platform …

2026/7/4 8:55:25 阅读更多 →
量子增强侧信道与迭代攻击:后量子密码(如McEliece)的混合威胁与防御实践

量子增强侧信道与迭代攻击:后量子密码(如McEliece)的混合威胁与防御实践

1. 项目概述:当量子计算遇上经典密码 最近在密码学圈子里,一个听起来有点“缝合怪”但又极具前瞻性的概念被反复提及——“量子相关密钥攻击迭代EM密码”。乍一看,这标题融合了“量子”、“密钥攻击”、“迭代”和“EM密码”几个硬核词汇&…

2026/7/4 8:55:25 阅读更多 →
Linux/WSL终端美化指南:gh_mirrors/do/dotfiles-archive的zsh与Hyper配置技巧

Linux/WSL终端美化指南:gh_mirrors/do/dotfiles-archive的zsh与Hyper配置技巧

Linux/WSL终端美化指南:gh_mirrors/do/dotfiles-archive的zsh与Hyper配置技巧 【免费下载链接】dotfiles-archive Dotfiles for all :D 项目地址: https://gitcode.com/gh_mirrors/do/dotfiles-archive gh_mirrors/do/dotfiles-archive项目提供了一套完整的终…

2026/7/4 8:55:25 阅读更多 →
高速PCB阻抗设计3大误区:线宽、铜厚与阻焊对±10%公差的实际影响

高速PCB阻抗设计3大误区:线宽、铜厚与阻焊对±10%公差的实际影响

高速PCB阻抗设计实战:破解线宽、铜厚与阻焊的10%公差迷思1. 阻抗设计的基础认知误区在高速PCB设计中,阻抗控制绝非简单的理论计算问题。许多工程师习惯将IPC标准中的公式直接套用,却忽略了实际制造环节中至少12个关键变量对最终阻抗值的影响。…

2026/7/4 8:55:25 阅读更多 →
PAT 乙级题目讲解:1006《换个格式输出整数》

PAT 乙级题目讲解:1006《换个格式输出整数》

✅ PAT 乙级题目讲解:1006《换个格式输出整数》摘要: 本文讲解 PAT 乙级真题 1006《换个格式输出整数》。题目要求将三位数按百位、十位、个位拆分,并分别以字母 B、S 和自然数序列输出。文章通过样例分析、分步拆解代码、完整实现、常见错误…

2026/7/4 8:51:24 阅读更多 →

日新闻

Memcached 1.6.43 发布:关键安全修复版本,多项问题得到解决

Memcached 1.6.43 发布:关键安全修复版本,多项问题得到解决

Memcached 1.6.43 正式发布,这是一个关键的安全修复版本,修复了多个方面的问题,还对部分功能进行了优化。 安全修复亮点 此次发布在安全修复上表现突出。binprot 避免了项目引用计数溢出,mcmc 因安全问题提升了上游版本号&#xf…

2026/7/4 0:04:29 阅读更多 →
终极指南:使用HMCL启动器跨平台畅玩Minecraft的完整解决方案

终极指南:使用HMCL启动器跨平台畅玩Minecraft的完整解决方案

终极指南:使用HMCL启动器跨平台畅玩Minecraft的完整解决方案 【免费下载链接】HMCL A Minecraft Launcher which is multi-functional, cross-platform and popular 项目地址: https://gitcode.com/gh_mirrors/hm/HMCL HMCL(Hello Minecraft! Lau…

2026/7/4 0:06:29 阅读更多 →
KMX63与PIC18F66K40在嵌入式HMI中的硬件协同与低功耗设计

KMX63与PIC18F66K40在嵌入式HMI中的硬件协同与低功耗设计

1. KMX63与PIC18F66K40的硬件协同架构解析KMX63作为一款三轴加速度计和磁力计组合传感器,与PIC18F66K40微控制器的搭配堪称嵌入式HMI开发的黄金组合。这套硬件组合的核心优势在于KMX63提供的高精度运动感知能力与PIC18F66K40强大的信号处理能力形成了完美互补。KMX6…

2026/7/4 0:06:29 阅读更多 →

周新闻

月新闻