Mükafatların toplanması#1619

Mükafatların toplanması (Həll təhlili)

Qutuları birincidən başlayaraq yenidən nömrələyək ( $i$ -ci qutu $a_{i}$ a_i xalını ehtiva edir). Gəlin $f (i)$ funksiyasını $1$ -dən $i$ -ci qutuya qədər olan qutuları daxil edərək əldə edilə bilən maksimal xal cəmi kimi təyin edək.

Onda:

$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)$ hesablarkən iki halı nəzərdən keçirək:

əgər $i$ -ci qutu seçilibsə, onda qonşu $(i - 1)$ (i - 1)-ci qutu əlçatmazdır. Bu halda maksimal xal cəmi $f (i - 2) + a_{i}$ f(i - 2) + a_i olacaq.
əgər $i$ -ci qutu seçilmirsə, onda maksimal xal cəmi $f (i - 1)$ f(i - 1) olacaq.

Beləliklə

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)$ -nin qiymətlərini $r es$ kütləsində saxlayacağıq. Problemin cavabı $f (n) = r es [n]$ f(n) = res[n] olacaq.

Nümunə

f(3) hesablanmasını nəzərdən keçirək

Əgər üçüncü qutunu açmasaq, sadəcə iki qutu üçün ən yaxşı nəticəni alacağıq: $f (2) = 6$ f(2) = 6.

Əgər üçüncü qutunu açsaq, onda ikinci açılabilməz (onlar qonşudur). Deməli, birinci qutu üçün optimal nəticəni götürüb üçüncü qutunun xalını əlavə edə bilərik:

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

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

İki variantdan maksimumu seçirik:

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) hesablanmasını nəzərdən keçirək

Əgər dördüncü qutunu açmasaq, nəticə $f (3) = 8$ f(3) = 8 olacaq.

Əgər dördüncü qutunu açsaq, üçüncüsü açılabilməz. Deməli, ilk iki qutu üçün ən yaxşı nəticəni alıb dördüncü qutudan xalları əlavə edirik:

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

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

İki variantdan maksimumu seçirik:

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

Məşq

Aşağıdakı giriş məlumatları üçün $f (i)$ -nin qiymətlərini hesablayın:

Alqoritmin reallaşdırılması

Gəlin giriş kütləsi $a$ və nəticə kütləsi $r es$ elan edək.

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

Giriş məlumatlarını oxuyuruq.

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

Bir $r e s_{1}$ res_1 və iki $r e s_{2}$ res_2 qutu üçün cavabı hesablayırıq.

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

Qalan qutular üçün cavabları hesablayırıq.

for (i = 3; i <= n; i++)
  res[i] = max(res[i - 2] + a[i], res[i - 1]);

Cavabı çıxışa veririk.

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

Java reallaşdırılması

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 reallaşdırılması

Giriş məlumatlarını oxuyuruq.

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

$d p$ siyahısını başlatırıq.

dp = [0] * len(lst)

Bir $d p_{0}$ dp_0 və iki $d p_{1}$ dp_1 qutu üçün cavabı hesablayırıq.

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

Qalan qutular üçün cavabları hesablayırıq.

for i in range(2, len(lst)):
  dp[i] = max(dp[i-1], dp[i-2] + lst[i])

Cavabı çıxışa veririk.

print(dp[-1])