Збір призів#1619

Збір призів (Розбір)

Перенумеруємо коробки, починаючи з першої ( $i$ -а коробка містить $a_{i}$ a_i очок). Нехай $f (i)$ позначає максимальну суму очок, яку можна отримати, розглядаючи коробки з $1$ по $i$ -у включно.

Тоді:

$f (1) = a_{1}$ f(1) = a_1,
$f (2) = ma x (a_{1}, a_{2})$ f(2) = max(a_1, a_2)

При обчисленні $f (i)$ розглянемо два випадки:

якщо обирається $i$ -а коробка, то сусідня $(i - 1)$ (i - 1)-а коробка недоступна. У цьому випадку максимальна сума очок буде дорівнювати $f (i - 2) + a_{i}$ f(i - 2) + a_i.
якщо $i$ -а коробка не обирається, то максимальна сума очок дорівнює $f (i - 1)$ f(i - 1).

Таким чином

f (i) = ma x (f (i - 2) + a_{i}, f (i - 1))

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

Запам'ятаємо значення $f (i)$ в масиві $r es$ . Відповіддю задачі буде значення $f (n) = r es [n]$ f(n) = res[n].

Приклад

Розглянемо обчислення f(3)

Якщо третю коробку не відкривати, то ми просто отримаємо найкращий результат для перших двох коробок: $f (2) = 6$ f(2) = 6.

Якщо третю коробку відкрити, то другу відкрити вже не можна (вони сусідні). Отже, можна взяти оптимальний результат для першої коробки і додати очки з третьої:

f (1) + a_{3} = 6 + 2 = 8

f(1) + a_3 = 6 + 2 = 8

Обираємо максимум з двох варіантів:

f (3) = ma x (f (2), f (1) + a_{3}) = ma x (6, 8) = 8

f(3) = max(f(2), f(1) + a_3) = max(6, 8) = 8

Розглянемо обчислення f(4)

Якщо четверту коробку не відкривати, то результат дорівнює $f (3) = 8$ f(3) = 8.

Якщо четверту коробку відкрити, то третю відкрити не можна. Отже, беремо найкращий результат для перших двох коробок і додаємо очки з четвертої:

f (2) + a_{4} = 6 + 10 = 16

f(2) + a_4 = 6 + 10 = 16

Обираємо максимум з двох варіантів:

f (4) = ma x (f (3), f (2) + a_{4}) = ma x (8, 16) = 16

f(4) = max(f(3), f(2) + a_4) = max(8, 16) = 16

Вправа

Обчисліть значення $f (i)$ для наступних вхідних даних:

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

Оголосимо вхідний масив $a$ та результуючий $r es$ .

#define MAX 1000001
long long a[MAX], res[MAX];

Читаємо вхідні дані.

scanf("%d",&n);
for (i = 1; i <= n; i++)
  scanf("%lld",&a[i]);

Обчислюємо відповідь для однієї $r e s_{1}$ res_1 та двох $r e s_{2}$ res_2 коробок.

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();
  }
}

Java

Python реалізація

Читаємо вхідні дані.

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

Ініціалізуємо список $d p$ .

dp = [0] * len(lst)

Обчислюємо відповідь для однієї $d p_{0}$ dp_0 та двох $d p_{1}$ dp_1 коробок.

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])