acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(0)
  • 思路

    可以使用动态规划来解决这个问题。 首先考虑状态。由于跳跳虎的位置和目标位置都在数轴上,可以将状态定义为f[i]表示跳到点i所需要的最少次数。 然后考虑转移。设当前已经跳到点i,上一次跳跃距离为x,需要跳到点j,则有以下几种情况: 1. j = i + 1,下一次跳跃距离为1,即x' = 1; 2. j = i - 1,下一次跳跃距离为1,即x' = 1; 3. j = i + x,下一次跳跃距离为x,即x' = x; 4. j = i + x - 1,下一次跳跃距离为x-1,即x' = x-1; 5. j = i + x + 1,下一次跳跃距离为x+1,即x' = x+1。 其中情况1和2是特殊情况,需要单独处理。对于其他情况,每次跳跃都是最优的,因为下一次跳跃距离只能比上一次更小或更大1。所以可以得到状态转移方程: f[j] = min(f[j], f[i]+1); x' = x-1, x, or x+1; j = i + x or i + x - 1 or i + x + 1 最终的答案为f[m]。

    userId_undefined

    看我干嘛

    倔强青铜
    72阅读
    2回复
    3点赞
首页