e-olymp 595. Новый Лабиринт Амбера

Задача

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от 1 до N. Из ячейки под номером i можно попасть в ячейки под номерами $i+2$ (если $i+2 ≤ N$) и $i+3$ (если $i+3 ≤ N$). На каждой ячейке лежит какое-то количество золотых монет $k_i$. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером N. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером N, вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

Входные данные

В первой строке входного файла содержится натуральное число $N$ $(2 ≤ N ≤ 100000)$, а во второй $N$ целых чисел, разделенных одним пробелом, $k_i$ – количество монеток лежащих в ячейке с номером $i (0 ≤ k_i ≤ 1000)$.

Выходные данные

В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.

Тесты

Входные данные Выходные данные
$5$
$1000$ $2$ $3$ $1$ $3$
$6$
$2$
$1$ $2$
$5610$
$4$
$1$ $3$ $100$ $0$
$3$

Код программы

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив $dp$ длиной $n + 1$ элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего значение первого элемента массива делаем отрицательным, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером $i$ он может попасть или из ячейки с номером $i — 2$, или из ячейки с номером $i — 3$. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения $i$-й ячейки имеет вид $dp_i = dp_i + max\{dp_{i — 2}; dp_{i — 3}\}$, и ответ к задаче хранится в $n$-й ячейке массива.

Ссылки

Условие задачи на e-olymp
Код решения

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *