Bilet alışı (Həll təhlili)

$t[i]$ ilə birinci müştəridən $i$-ci müştəriyə qədər olanları xidmətlə təmin etmək üçün lazım olan minimal vaxtı işarə edək. t[0] = 0 qəbul edək.

Əgər bir müştəri varsa, o, bileti özü a_1 saniyəyə alır, ona görə də t[1] = a_1.

İki müştəri üçün iki variant mümkündür: ya hər biri bileti ayrı-ayrılıqda a_1 + a_2 saniyəyə alır, ya da onlar birləşir və birinci iki bileti b_1 saniyəyə alır. Deməli, t[2] = min(a_1 + a_2, b_1).

Üç və daha çox müştəri olduqda şərtdə təsvir edilən bütün birləşmə üsulları mümkündür, ona görə də aşağıdakı rekurrent asılılığı alırıq:

Burada:

• Əgər $i$-ci müştəri bileti özü alırsa, t[i - 1] + a_i vaxtı sərf olunur.

• Əgər (i - 1)-ci müştəri iki bilet alırsa (özü üçün və $i$-ci üçün), t[i - 2] + b_{i-1} vaxtı sərf olunur.

• Əgər (i - 2)-ci üç bilet alırsa (özü, (i - 1)-ci və $i$-ci üçün), t[i - 3] + c_{i-2} vaxtı sərf olunur.

Üç ifadədən minimumu seçmək qalır — bu, ilk $i$ müştərinin bilet ala biləcəyi ən kiçik vaxt olacaq.

Alqoritmin realizasiyası

a_i, b_i, c_i dəyərlərini uyğun olaraq a, b, c massivlərində saxlayacağıq.

#define MAX 5010
int a[MAX], b[MAX], c[MAX], t[MAX];

Giriş məlumatlarını oxuyuruq.

scanf("%d",

for (i = 1; i \<= n; i++) scanf("%d %d %d",

Başlanğıc dəyərləri təyin edək.

t[0] = 0; t[1] = a[1]; t[2] = min(a[1] + a[2],b[1]);

Sonra dövrdə $t[i]$ dəyərlərini hesablayırıq.

for (i = 3; i \<= n; i++)
  t[i] = min(t[i-1] + a[i], t[i-2] + b[i-1], t[i-3] + c[i-2]);

Nəticəni çap edirik. Birinci müştəridən $n$-ciyə qədər bütün müştəriləri xidmətlə təmin etmək üçün minimal vaxt $t[n]$-ə bərabərdir.

printf("%d\n",t[n]);

Java realizasiyası

import java.util.*;

public class Main
{
  public static int MAX = 5010;
  static int a[] = new int[MAX];
  static int b[] = new int[MAX];
  static int c[] = new int[MAX];
  static int t[] = new int[MAX];

  public static int min(int a, int b, int c)
  {
    return Math.min(Math.min(a,b),c);
  }
  
  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();
      b[i] = con.nextInt();
      c[i] = con.nextInt();
    }
    
    t[0] = 0; t[1] = a[1]; t[2] = Math.min(a[1] + a[2],b[1]);
    for (int i = 3; i \<= n; i++)
      t[i] = min(t[i-1] + a[i], t[i-2] + b[i-1], t[i-3] + c[i-2]);

    System.out.println(t[n]);
    con.close();
  }
}

Python realizasiyası

Müştərilərin sayı $n$-i oxuyuruq.

n = int(input())

a_i, b_i, c_i dəyərlərini uyğun olaraq a, b, c siyahılarında saxlayacağıq.

a = [0] * 5001
b = [0] * 5001
c = [0] * 5001
for i in range(1,n+1):
  a[i], b[i], c[i] = map(int, input().split())

Başlanğıc dəyərləri təyin edək.

t = [0] * (n+1)
t[0] = 0;
t[1] = a[1];
if n > 1 : t[2] = min(a[1] + a[2], b[1]);

Sonra dövrdə $t[i]$ dəyərlərini hesablayırıq.

for i in range(3, n+1):
  t[i] = min(t[i-1] + a[i], t[i-2] + b[i-1], t[i-3] + c[i-2])

Nəticəni çap edirik. Birinci müştəridən $n$-ciyə qədər bütün müştəriləri xidmətlə təmin etmək üçün minimal vaxt $t[n]$-ə bərabərdir.

print(t[-1])