-1

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

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

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю у героя уходит |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)
1
  • Заголовок должен отражать содержание темы
    – MBo
    Commented 23 июн. 2021 в 2:19

1 ответ 1

2

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

Допустим, у нас есть некоторое количество платформ, высоты которых занесены в список. Тогда представим, что последняя платформа у нас хранится под индексом i, а её высота равна y. На i-тую платформу мы можем попасть только с двух предыдущих платформ, т.е. с платформ i-1 и i-2. Их высоты соответственно yi-1 и yi-2. Необходимую энергию для прыжка с одной платформы на другую мы знаем из условия задачи. Чтобы попасть на i-тую платформу с платформы i-1 нам нужно потратить модуль разницы их высот, т.е. |y - yi-1|. А чтобы попасть на i-тую платформу с платформы i-2 нам нужно потратить утроенный модуль разницы их высот, т.е. 3*|y - yi-2|. К данным выражениям прибавляем энергию (пусть она будет Е), которую затратили на посещение этих клеток, т.е. энергии клетки i-1 и i-2 соответственно.
Получаем следующее выражение
Еi = min(|y-yi-1| + Еi-1, 3*|y-yi-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
4
  • Вы так хорошо ответили, что я даже смог свою прогу написать по вашим формулам и раскладкам, спасибо Commented 22 июн. 2021 в 18:49
  • Если ответ помог, его стоит принять - пометить галочкой как верный.
    – MBo
    Commented 23 июн. 2021 в 2:21
  • Я не могу, репутации неи Commented 23 июн. 2021 в 3:59
  • Принимать ответ на свой вопрос - репутация не нужна
    – MBo
    Commented 23 июн. 2021 в 6:56

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.