HBC20078[HNOI2009]通往城堡之路题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

幸运的是，彭大侠还有一个杀手锏，在起点处，他可以花一个金币，把某个支撑点升高1个单位，或者降低1个单位，但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点彭大侠就无法使用该杀手锏， 彭大侠被告知100个金币可兑换一单位生命，于是他希望通过少花金币来保存更多单位的生命，他终于找到了你这位热心的高手，请你帮他规划一下以便耗费尽量少的金币来到达城堡。

听说公主被关押在城堡里，彭大侠下定决心：不管一路上有多少坎坷，不管城堡中的看守有多少厉害，不管救了公主之后公主会不会再被抓走，不管公主是否漂亮、是否会钟情于自己，他将义无反顾地朝着城堡前进。      可是，通往城堡的路上出现了一些情况。抽象地说，假象地图在二维平面的第一象限。在每个横轴的x位置上有一个高为hx的支撑点，如果彭大侠没有跳到支撑点上，那么他就会掉下去，牺牲在路途。 开始时彭大侠在起点（1，h1）处，而城堡的入口在（n，hn）处。彭大侠每次可以从支撑点（x，hx）跳到支撑点（x+1，hx+1）。但是彭大侠每次的跳跃能量只有d，也就是说，每次跳跃必须满足条件|hx+1-hn| ≤ d。换句话说，如果两个相邻支撑点的纵向落差大于d，那么彭大侠就无法跳跃了！幸运的是，彭大侠还有一个杀手锏。在起点处，他可以花一个金币，把某个支撑点升高1个单位，或者降低1个单位。但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点彭大侠就无法使用该杀手锏。      彭大侠被告知100个金币可兑换一单位生命。于是他希望通过少花金币来保存更多单位的生命。他终于找到了你这位热心的高手，请你帮他规划一下以便耗费尽量少的金币来到达城堡。

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC20078[HNOI2009]通往城堡之路题解