距离蓝桥杯还有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时都要大所以不能进队。所以也很容易想到当队列为空所有路径都走完了且找不到更加小的值了达到了优化的目标。以上是我关于蓝桥杯中调手表问题的所有思考了欢迎讨论。