Buying tickets (Editorial)

Let $t[i]$ denote the minimum time required to serve the first $i$ customers. Set t[0] = 0.

If there is one customer, they buy a ticket individually in a_1 seconds, so t[1] = a_1.

For two customers, there are two possible options: either each customer buys a ticket separately, taking a_1 + a_2 seconds in total, or they form a group, and the first customer buys two tickets in b_1 seconds. Therefore, t[2] = min(a_1 + a_2, b_1).

When there are three or more customers, all the grouping options described in the problem statement are possible, so we obtain the following recurrence relation:

Here:

• If the $i$-th customer buys a ticket individually, the required time is t[i - 1] + a_i.

• If the (i - 1)-th customer buys two tickets (one for themselves and one for the $i$-th customer), the required time is t[i - 2] + b_{i-1}.

• If the (i - 2)-th customer buys three tickets (one for themselves, one for the (i - 1)-th customer, and one for the $i$-th customer), the required time is t[i - 3] + c_{i-2}.

It remains to choose the minimum of these three expressions. This will be the minimum time required for the first $i$ customers to purchase their tickets.

Algorithm implementation

Store the values a_i, b_i, c_i in the arrays a, b, c respectively.

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

Read the input data.

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

Initialize the starting values.

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

Then, compute the values of $t[i]$ in a loop.

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

Finally, print the result. The minimum time required to serve all customers from the first to the $n$-th is $t[n]$.

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

Java implementation

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 implementation

Read the number of customers $n$.

n = int(input())

Store the values a_i, b_i, c_i in the lists a, b, c respectively.

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

Initialize the starting values.

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

Then, compute the values of $t[i]$ in a loop.

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

Print the result. The minimum time required to serve all customers from the first to the $n$-th is $t[n]$.

print(t[-1])