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

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

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

Вход. Первая строка содержит количество домов n (1 ≤ n ≤ 10⁶). Вторая строка содержит n целых неотрицательных чисел a₁, a₂, ..., a_n, где a_i – количество денег, которое может быть вынесено из i-го дома.

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

Пример входа	Пример выхода
5 6 1 2 10 4	16

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Перенумеруем дома начиная с первого индекса (i-ый дом содержит a_i денег). Пусть f(i) – максимальная сумма добычи после грабежа домов с 1 по i-ый.

Тогда f(1) = a₁, f(2) = max(a₁, a₂).

При вычислении f(i) рассмотрим два случая:

· если i-ый дом грабится, то (i – 1)-ый дом трогать нельзя. В таком случае прибыль составит f(i – 2) + a_i.

· если i-ый дом не грабится, то прибыль составит f(i – 1).

Таким образом

f(i) = max(f(i – 2) + a_i, f(i – 1))

Запомним значения f(i) в массиве res. Ответом задачи будет значение f(n) = res[n].

Пример

Рассмотрим вычисление f(3). Если третий дом мы не грабим, то прибыль составит f(2) = 6. Если третий дом грабится, то можно ограбить первый дом, получив прибыль f(1) = 6 плюс прибыль за ограбление третьего дома, равную 2 (общая прибыль составит 6 + 2 = 8).

Рассмотрим вычисление f(4). Если четвертый дом мы не грабим, то прибыль составит f(3) = 8. Если четвертый дом грабится, то можно ограбить первые два дома, получив прибыль f(2) = 6 плюс прибыль за ограбление четвертого дома, равную 10 (общая прибыль составит 6 + 10 = 16).

Упражнение

Вычислите значения f(i) для следующих входных данных:

Реализация алгоритма

Объявим входной массив а и результирующий res.

#define MAX 1000001

long long a[MAX], res[MAX];

Читаем входные данные.

scanf("%d",&n);

for(i = 1; i <= n; i++)

scanf("%lld",&a[i]);

Вычисляем ответ для одного res₁ и двух res₂ домов.

res[1] = a[1];

if (n > 1) res[2] = max(a[1],a[2]);

Вычисляем ответы для остальных домов.

for(i = 3; i <= n; i++)

res[i] = max(res[i - 2] + a[i], res[i - 1]);

Выводим ответ.

printf("%lld\n",res[n]);

Java реализация

import java.util.*;

class Main

{

static long a[] = new long[1000001];

static long res[] = new long[1000001];

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

for(int i = 1; i <= n; i++)

a[i] = con.nextInt();

res[1] = a[1];

if (n > 1) res[2] = Math.max(a[1],a[2]);

for(int i = 3; i <= n; i++)

res[i] = Math.max(res[i - 2] + a[i], res[i - 1]);

System.out.println(res[n]);

con.close();

}

}

Python реализация

Читаем входные данные.

n = int(input())

lst = list(map(int,input().split()))

Инициализируем список dp.

dp = [0] * len(lst)

Вычисляем ответ для одного dp₀ и двух dp₁ домов.

dp[0] = lst[0]

if (n > 1): dp[1] = max(lst[0], lst[1])

Вычисляем ответы для остальных домов.

for i in range(2, len(lst)):

dp[i] = max(dp[i-1], dp[i-2] + lst[i])

Выводим ответ.

print(dp[-1])