e-olymp 806. Платформы — 3

Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

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

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

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

Выведите единственное целое число — искомую величину энергии.

Тесты

Входные данные  Выходные данные
1 4
1 2 3 30
731
2 4
0 1 6 8
40
3 8
1 15 16 23 42 10 84 5
828
4 7
57 54 -55 -34 21 88 -100
55189
5 7
-4000 4000 -4000 4000 -4000 4000 -4000
0

Код программы

Решение

Чтобы решить задачу, мы создадим массив $energy$, где будем хранить минимальную энергию, которую герой потратит для прыжка на очередную $i$-ю платформу. Для этого необходимо для каждой платформы, начиная со второй, рассмотреть три вида прыжка:

  • прыжок с предыдущей $i — 1$ платформы.
  • суперприём, то есть прыжок c $i — 2$ платформы.
  • 3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней  $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

2 thoughts on “e-olymp 806. Платформы — 3

    • Давайте более свободно подойдем к воспроизведению условия. В отличие от автора у нас есть возможность правильно записать математические формулы. Исправьте, пожалуйста.
    • У Вас довольно неплохое объяснение. Вот только не ясно, это формулы в laTeX или код в С++? Там какая-то смесь. Я не знаю как лучше. Возможно проще всего было бы сделать нормальные формулы обозначив platforms[i] через $p_i$? А то вроде массив, а выглядит как формула и вставлен в формулу. Как Вы считаете?
    • Пожалуйста, загрузите изображение на сайт. Не нужно использовать ссылки в сети, которые в любой момент перестанут работать.
    • Спасибо, исправила недочеты. Насчет формул, я считаю, лучше и проще придерживаться обозначений высот, как в условии, и только в laTeX.

Добавить комментарий