Задача
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|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 27 28 29 30 31 32 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); long j, sj, bj; // цены прыжка, суперприема и 3-го типа прыжка int[] platforms = new int [n]; long[] energy = new long[n]; // создаем массивы для платформ и энергии for (int i = 0; i < n; ++i) platforms[i] = in.nextInt(); //считываем высоты платформ energy[0] = 0; for (int i = 1; i < n; ++i) { // обычный прыжок j = (platforms[i] - platforms[i-1]) * (platforms[i] - platforms[i-1]); // 3-й тип прыжка if (i != n-1) bj = (platforms[i] - platforms[i+1]) * (platforms[i] - platforms[i+1]) + 3 * (platforms[i+1] - platforms[i-1]) * (platforms[i+1] - platforms[i-1]); else bj = j; // суперприём if (i == 1) sj = Math.max(j, bj); else sj = 3 * (platforms[i] - platforms[i-2]) * (platforms[i] - platforms[i-2]); if (i == n-1) bj = Math.max(j, sj); //количество энергии на i-й платформе if (i == 1) energy[i] = Math.min(energy[i-1] + bj, energy[i-1] + j); else energy[i] = Math.min(energy[i-1] + bj, Math.min(energy[i-1] + j, energy[i-2] + sj)); } System.out.println(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}$.