信息
- ID
- 1
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 200
- 已通过
- 61
- 上传者
其实就是一道二位费用 dp。
用 dp0,i 表示从开始跳跃位置跳到第 i 层不用法力的最短时间,dp1,i 表示从开始跳跃位置跳到第 i 层用法力的最短时间。
很显然可以得到 dp 式:
dp0,i=min(dp0,i−1,dp1,i−1)+ai dp1,i=min(dp0,i−1,dp0,i−2)+0注意:用了法力就不能继续用法力,必须先爬一层过后才能使用法力。
因此可以得到如上 dp 式。
答案即为 min(dp0,n,dp1,n)。
LC 大佬 AKIOI!(同 wcj 的意思)