Вася придумал игру, в которой герой должен добраться до финиша, прыгая по платформам. Прыжок может быть на соседнюю или через одну платформу. В первом случае затрачивается |х2-х1|, а во втором 3*|х2-х1| едениц энергии, где х1 и х2- высоты платфор, с которой и на которую совершается прыжок. Какое минимальное количество энергии герой потратит, чтобы перебраться на конечную платформу, начав с первой? Дано 8 платформ и высоты 1пл=10 2пл=15 3пл=9 4пл=18 5пл=7 6пл=18 7пл=7 8 пл=19

Предыдущий
вопрос Следующий
вопрос

Для того чтобы минимизировать количество потраченной энергии, герою нужно выбирать прыжки с меньшим затрачиваемым количеством энергии.

Минимальное количество потраченной энергии можно найти, используя динамическое программирование. Для этого будем вычислять минимальное количество энергии для достижения каждой платформы, начиная с первой.

Итак, для данного случая минимальное количество энергии, которое герой потратит, чтобы добраться до последней платформы, равно 32.

1 -> 2 (|15-10| = 5)
1 -> 3 -> 4 -> 6 -> 8 (|9-10| + |18-9| + |18-18| + |19-18| = 1 + 9 + 0 + 1 = 11)
1 -> 3 -> 4 -> 6 -> 7 -> 8 (|9-10| + |18-9| + |18-18| + |7-18| + |19-7| = 1 + 9 + 0 + 11 + 12 = 33)
1 -> 4 -> 6 -> 8 (|18-10| + |18-18| + |19-18| = 8 + 0 + 1 = 9)
1 -> 4 -> 5 -> 6 -> 8 (|18-10| + 3*|7-18| + |18-7| + |19-18| = 8 + 33 + 11 + 1 = 53)

Таким образом, наименьшее количество энергии, чтобы добраться до последней платформы, равно 32.