Как решить задачу

Question

Снова хочу попросить помочь с задачей

Компьютерная игра Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно.

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю у героя уходит |y2–y1| единиц энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается 3⋅|y3–y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

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

Входные данные

В первой строке записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 — высоты, на которых располагаются платформы.

Выходные данные

Выведите единственное число — минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же, в предположении, что cheat-коды использовать нельзя).

Примеры

Ввод 1
2
100 1
Вывод
99

Ввод 2
3
1 100 80
Вывод
119

Так же прилагаю свой код

n, k = map(int, input().split())
a, b = k-1, 1
for _ in range(n-1):
    a, b = (a + b) * (k-1), a
print(a + b)

Answer 1

Что требуется для решения этой задачи? По сути, вычислить наименьшую энергию требуемую для попадания на последнюю платформу.
Как это сделать? Узнать количество энергии требуемой для попадания на две предыдущие платформы и выбрать минимальную.

Допустим, у нас есть некоторое количество платформ, высоты которых занесены в список. Тогда представим, что последняя платформа у нас хранится под индексом i, а её высота равна y. На i-тую платформу мы можем попасть только с двух предыдущих платформ, т.е. с платформ i-1 и i-2. Их высоты соответственно y_i-1 и y_i-2. Необходимую энергию для прыжка с одной платформы на другую мы знаем из условия задачи. Чтобы попасть на i-тую платформу с платформы i-1 нам нужно потратить модуль разницы их высот, т.е. |y - y_i-1|. А чтобы попасть на i-тую платформу с платформы i-2 нам нужно потратить утроенный модуль разницы их высот, т.е. 3*|y - y_i-2|. К данным выражениям прибавляем энергию (пусть она будет Е), которую затратили на посещение этих клеток, т.е. энергии клетки i-1 и i-2 соответственно.
Получаем следующее выражение
Е_i = min(|y-y_i-1| + Е_i-1, 3*|y-y_i-2| + Е_i-2).

Ну и реализация этого алгоритма

def calc_min_energy(platforms):
    count = len(platforms)
    # если платформа всего одна, то и прыгать не нужно
    if count == 1: return 0
    # в energy[0] - суммируется минимальная энергия для посещения платформы i-2
    # в energy[1] - суммируется минимальная энергия для посещения платформы i-1
    # инициализируется энергиями требуемыми для посещения 0 и 1 платформ соответственно
    energy = [0, abs(platforms[1] - platforms[0])]
    for i in range(2, count):
        # считается минимальная энергия требуемая для посещения i-ой платформы 
        # на основе сохранённых энергий для посещений платформ i-1 и i-2
        # сохраняем эту энегрию и энергию для предыдущей платформы для последуещего шага
        energy = [energy[1], min(    abs(platforms[i] - platforms[i-1]) + energy[-1], 
                                 3 * abs(platforms[i] - platforms[i-2]) + energy[-2])]
    # результат - энергия для последней платформы
    return energy[-1]

print(calc_min_energy([100,1]))
print(calc_min_energy([1,100,80]))
print(calc_min_energy([1,100,80,5,6,7,8,23,5,3,4,3,2,1,11,12,13,14,15,10,8,0]))

Результат

99
119
239

БЛОГ НА HUSL

Как решить задачу

Ответы (1 шт):