Задача
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; int main() { int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка cin >> n; int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии for (int i = 0; i < n; ++i) { cin >> platforms[i]; //считываем высоты платформ } energy[0] = 0; for (int i = 1; i < n; ++i) { // обычный прыжок j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]); // 3-й тип прыжка bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) + 3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]); // суперприём if (i == 1) sj = max(j, bj); else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]); if (i == n - 1) bj = max(j, sj); //количество энергии на i-й платформе energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj)); } cout << energy[n - 1]; } |
Решение
Чтобы решить задачу, мы создадим массив $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
Спасибо, исправила недочеты. Насчет формул, я считаю, лучше и проще придерживаться обозначений высот, как в условии, и только в laTeX.