Задача Platforms
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. В одной из версий данной игры, при прыжке с платформы на соседнюю, у героя уходит |y2–y1| энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3×|y3–y1| энергии. Другая версия отличается только тем, что в функциях затрат энергии модули заменены на квадраты, т. е. (y2–y1)2 при прыжке на соседнюю и 3×(y3–y1)2 при прыжке через одну. Известны высоты платформ в порядке от левого края до правого. Найдите (для каждой из версий игры) минимальное количество энергии, достаточное, чтобы добраться с 1-й платформы до n-й (последней).
Технические условия:
Программа должна прочитать с клавиатуры сначала количество платформ N (2≤N≤50000), затем N чисел в диапазоне от –2000 до +2000 каждое — высоты этих платформ. Программа должна вывести на экран в единственной строке два разделенных пробелом целых числа — минимальные необходимые затраты энергии для первой версии игры и для другой версии игры.
Пример:
Ввод: 3 0 20 11
Вывод: 29 363
Для первой версии оказывается выгоднее прыгать по всем подряд платформам 0→20→11, суммарные затраты 20+9=29. Для второй — перепрыгнуть сразу 0→11 выгоднее (3*112=363), чем прыгать по всем платформам подряд (202+92=481).
|
