Условие
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.
Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.
Входные данные
Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.
Выходные данные
В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.
Тесты
| № | Ввод | Вывод |
| 1 | 4 1 2 3 30 |
29 4 1 2 3 4 |
| 2 | 2 7 23 |
16 2 1 2 |
| 3 | 5 0 1 0 1 0 |
0 3 1 3 5 |
Код
|
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 33 34 35 36 37 38 |
import java.util.Scanner; class Main{ public static void main (String[] args) { final int MAX = 100001; Scanner sc = new Scanner(System.in); int amount_of_pltf = sc.nextInt(); int[] energy, platforms, list_of_pltf; int[] heights = new int[MAX]; for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt(); energy = new int[MAX]; platforms = new int[MAX]; energy[1] = 0; energy[2] = Math.abs(heights[2] - heights[1]); platforms[1] = -1; platforms[2] = 1; //В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf) for (int j = 3; j <= amount_of_pltf; j++){ if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){ energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]); platforms[j] = j - 1; } else { energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]); platforms[j] = j - 2; } } //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти. int final_amount = 0; list_of_pltf = new int[MAX]; for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l; System.out.println(energy[amount_of_pltf] + "\n" + final_amount); for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " "); } } |
Решение
Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:
- Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
- Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».
Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.
Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.
Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.