Вася придумал игру, в которой герой должен добраться до финиша, прыгая по платформам....

Question

Вася придумал игру, в которой герой должен добраться до финиша, прыгая по платформам. Прыжок может быть на соседнюю платформу или через одну платформу. В первом случае затрачивается х2-х1, а во втором 3(х2-х1) единиц энергии, где х1 и х2 - высоты платформ, с которой и на которую совершается прыжок. Какое минимальное количество энергии герой потратит, чтобы перебраться на конечную платформу, начав с первой?

---

Comments

Вопрос: если х2>x1, то энергия затрачивается. А если х2<=x1, то энергия дополнительная получается? Или надо брать абсолютную величину разности?

---

А задача сводится к построению графа и поиску кратчайшего пути на нем.

Answer 1

16, если использовать 3 прыжка через одну и 1 на следующуу