Призы в школьном коридоре

В школе поставили вдоль коридора ряд ящиков с призами. В i-м ящике лежит приз ценностью ai.

Но есть правило: если открыть какой-то ящик, то два соседних с ним ящика сразу блокируются (шум, датчики и всё такое). Поэтому за один проход по коридору нельзя открыть два соседних ящика.

Найди максимальную суммарную ценность призов, которую можно забрать.

Важно: суммарная ценность может не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битные числа. В Python это не проблема.

Формат ввода

Первая строка: целое число n — количество ящиков. Вторая строка: n целых чисел a1, a2, ..., an.

Формат вывода

Одно число — максимальная суммарная ценность.

Ограничения

• 1 ≤ n ≤ 3000
• 0 ≤ ai ≤ 100000

Пример

Ввод:

5
2 7 9 3 1

Вывод:

12

Пояснение: можно открыть ящики с ценностями 2, 9 и 1 (они не соседние), получим 12.

Ключевое наблюдение: решение для первых i ящиков зависит только от того, взяли ли мы i-й. Если i-й ящик взяли, то (i-1)-й брать нельзя — правило про соседей.

Отсюда естественно получается динамическое программирование (ДП): идём слева направо и храним лучший результат на префиксе в двух состояниях.

Идея переходов:

• dp0 — максимум для уже просмотренных ящиков, если текущий НЕ взяли.
• dp1 — максимум, если текущий ВЗЯЛИ.

Тогда при обработке значения x:

• чтобы взять текущий, предыдущий обязан быть не взят: new_dp1 = dp0 + x
• чтобы не брать текущий, можно прийти из любого состояния: new_dp0 = max(dp0, dp1)

В конце ответ — max(dp0, dp1).

План решения:

• Прочитать n и массив a.
• Инициализировать dp0 = 0, dp1 = 0.
• Для каждого x из a пересчитать new_dp0, new_dp1, затем заменить старые значения.
• Вывести max(dp0, dp1).

Сложность: O(n) по времени, O(1) по памяти — удобно при n до 3000.

Частая ошибка: делать dp1 = dp1 + x (как будто можно брать соседние). Обязательно брать из dp0, иначе вы разрешите запрещённые пары.