Task 93. Очередь за билетами

Задача: За билетами в кино выстроилась очередь из N человек. Кассир продает не более 3х билетов в одни руки. Известно, что на продажу i-му человеку из очереди 1го билета кассир тратит Ai секунд, на продажу 2х билетов - Bi секунд, 3х билетов - Ci секунд. 

Необходимо выяснить минимальное время, за ктр все покупатели могли бы приобрести билеты.

P.S. Билеты на "группу" людей всегда покупает только первый из группы. Также никто в целях ускорения не покупает лишних билетов (т.е. билетов, ктр никому не нужны).

Входные данные: N - кол-во покупателей в очереди, N меньше 1000.

A, B, C - массивы натуральных чисел, ктр хранят значения времени продажи одного, двух и трех билетов i-му покпателю. Значения в массиве не превышают 1000.

Вывод: минимальное время, за ктр все покупатели смогут приобрести билеты.

Пример: N = 5;

A = [5, 2, 5, 20, 20]

B = [10, 10, 5, 20, 1]

C = [15, 15, 5, 1, 1]

MinTime = 12

Идея: воспользуемся методом динамического программирования:

заведем массив time, в time[i] будем хранить минимальное время, за ктр можно продать билеты от 1го покупателя до i-го. 

Разберем частные случаи:

• Для одного покупателя очевидно, что time[1] = A[0]. Для удобства расчетов пусть time[0] = 0.
• Два покпателя смогут взять билеты по отдельности, и тогда время будет A[0] + A[1]. (нумерация с 0). Либо они могут договориться и тогда первый покупатель возьмет два билета за B[0] сек. Получим формулу для 2х покупателей:

time[2] = Min(A[0] + A[1], B[0])

• Для 3х и более покупателей получим обобщенную формулу:

time[i] = Min(time[i - 1] + A[i - 1], time[i - 2] + B[i - 2], time[i - 3] + C[i - 3])

Нумерация идет с 0, но для удобства расчетов мы положили, что time[0] = 0.

Реализация:

https://gist.github.com/unilecs/57ab6fe46116a56697e39e7524525ef6

Test:

https://dotnetfiddle.net/CCfsUp

Задача с сайта: acmp.ru