Задача №3781. Компьютерная игра (платформы) с восстановлением пути
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит |y2–y1| энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3·|y3–y1| энергии.
Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с 1-й платформы до n-й (последней) и список (последовательность) платформ, по которым нужно пройти.
Первая строка содержит количество платформ N (2 ≤ N ≤ 100000), вторая — N целых чисел, значения которых не превышают по модулю 4000 — высоты платформ.
В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите последовательность этих платформ.
Разумеется, в этой задаче для некоторых входных данных возможны разные правильные последовательности платформ. Ваша программа должна выводить любую одну из них.
4 1 2 3 30
29 4 1 2 3 4
10 1 100 1 100 1 100 1 100 1 100
99 6 1 2 4 6 8 10