Купівля квитків (Розбір)

Позначимо через $t[i]$ мінімальний час, за який можна обслужити покупців з першого по $i$-го. Покладемо t[0] = 0.

Якщо є один покупець, він купує квиток самостійно за a_1 секунд, тому t[1] = a_1.

Для двох покупців можливі два варіанти: або кожен купує квиток окремо за a_1 + a_2 секунд, або вони об'єднуються, і перший купує два квитки за b_1 секунд. Отже, t[2] = min(a_1 + a_2, b_1).

За наявності трьох і більше покупців можливі всі описані в умові способи об'єднання, тому отримуємо рекурентне співвідношення:

Тут:

• Якщо $i$-ий покупець купує квиток самостійно, витрачається час t[i - 1] + a_i.

• Якщо (i - 1)-ий покупець купує два квитки (для себе і для $i$-го), витрачається час t[i - 2] + b_{i-1}.

• Якщо (i - 2)-ий купує три квитки (для себе, (i - 1)-го і $i$-го), витрачається час t[i - 3] + c_{i-2}.

Залишається обрати мінімум із трьох виразів — це і буде найменший час, за який перші $i$ покупців зможуть придбати квитки.

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

Значення a_i, b_i, c_i будемо зберігати в масивах a, b, c відповідно.

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

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

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

Встановимо початкові значення.

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

Далі в циклі обчислюємо значення $t[i]$.

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$-го, дорівнює $t[n]$.

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

Java реалізація

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 реалізація

Читаємо кількість покупців $n$.

n = int(input())

Значення a_i, b_i, c_i будемо зберігати у списках a, b, c відповідно.

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

Встановимо початкові значення.

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

Далі в циклі обчислюємо значення $t[i]$.

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$-го, дорівнює $t[n]$.

print(t[-1])