e-olymp 1619. Ограбление домов

Задача

Вы – профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить – так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.

Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.

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

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 106)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

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

Выведите максимальную сумму, которую Вы сможете ограбить сегодня вечером без поступления сигнала в полицию.

Тесты

Входные данные Выходные данные
1 5
6 1 2 10 4
16
2 10
4 1 29 0 14 8 31 12 7 5
85
3 2
1 3
3

Код

Решение

Данная задача, это типичный пример применения динамического программирования.
Динамическое программирование — это метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой.

Решение задачи динамическим программированием должно содержать следующее:
Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям, либо к задаче, решаемой элементарно.
Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии. В противном случае вы можете попытаться узнать какой-то известный числовой ряд, вычислив первые несколько значений вручную.

Для решения данной задачи будет использовать метод последовательного вычисления (далее МПВ).
МПВ подходит, только если функция ссылается исключительно на элементы перед ней — это его основной минус.
Суть метода в следующем: необходимо создать массив на N элементов и последовательно заполнять его значениями. Таким образом вычисляется, в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения.

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

Следовательно, значения начальных состояний будут такими:
— Для первого дома — количество денег в нем.
— Для второго — максимальное количество денег из первых двух домов.

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

Ссылки

One thought on “e-olymp 1619. Ограбление домов

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