Автор: С.В. Шедов

Попробуем найти решение задачи, постепенно увеличивая размер очереди. Пусть у нас в очереди стоит всего один человек. Поскольку каждому человеку нужен один и только один билет (даже если 2 или 3 билета купить быстрее), то ответом задачи будет число A₁.

Теперь перейдем к очереди из 2 человек. Они могут купить билеты раздельно, тогда время покупки составит A_{1 ­­}+ A₂. Кроме того, они могут объединиться и купить билеты вместе, причем купить два билета по условию задачи может только первый человек. Из двух возможностей выбираем такую, которая займет меньше времени и запоминаем это время в элементе D[2] специального массива. Таким образом, D[2] – минимальное время покупки билетов очередью из 2 первых человек.

Добавим в очередь третьего человека. Какие варианты есть у нас? Если третий человек покупает билет самостоятельно, то первые два, очевидно, не зависят от него. Тогда (внимание!) мы уже решили эту задачу! Мы только что нашли минимальное время покупки билетов для очереди из двух человек, оно хранится в D[2]. Общее время покупки в этом случае составит D[2]+A_3­. Допустим, второй и третий человек решат купить билеты вместе. Ответом в этом случае будет B₂ + A₁ (два билета покупает второй человек и первый человек покупает билет самостоятельно). Наконец, договориться смогут и все три человека. Тогда они купят билеты за C₁ – именно столько времени займет покупка трех билетов у первого стоящего в очереди человека. Запишем лучший вариант в D[3] – это будет минимальное время покупки билетов очередью из 3 первых человек.

Рассмотрим все вышесказанное на примере из условия.

N=5

i	Ai	Bi	Ci
1	5	10	15
2	2	10	15
3	5	5	5
4	20	20	1
5	20	1	1

Заполним массив D начальными значениями, D[1] = A₁, остальные элементы пока неизвестны.

D[1]	D[2]	D[3]	D[4]	D[5]
5	???	???	???	???

Переходим к выяснению значения D[2]. Имеем, что при покупке билетов раздельно время составит A_{1 ­­}+ A_2­ = 5 + 2 = 7, а при покупке вместе - 10. Итак, D[2]=min(7,10)=7

D[1]	D[2]	D[3]	D[4]	D[5]
5	7	???	???	???

Добавляем в очередь третьего человека. Если он покупает билет отдельно, то общее время равно D[2] + A₃ = 7 + 5 = 12. Если второй и третий договариваются между собой, то общее время будет
D[1] + B₂ = 5 + 10 = 15. Наконец, в случае совместной покупки билетов тремя любителями мюзиклов, им удастся это сделать за время C₁ = 15. Разумеется, выбираем самый быстрый вариант и в данном случае D[3]=min(12,15,15)=12.

D[1]	D[2]	D[3]	D[4]	D[5]
5	7	12	???	???

Дальше будем действовать совершенно аналогично. Добавляем к очереди четвертого человека. Выпишем формулу для D[4].

D[4] = min ( D[3]+A₄ , D[2] + B₃ , D[1] + C₂ )

Итак, D[4]=min(12+20, 7+5, 5+15)=min(32, 12, 20)=12

D[1]	D[2]	D[3]	D[4]	D[5]
5	7	12	12	???

Продолжая рассуждения аналогично, в общем виде получаем следующую формулу:

D[i] = min ( D[i-1]+Ai , D[i-2] + Bi-1 , D[i-3] + Ci-2 )

Ответом к задаче будет служить элемент массива D[N]. В нашем случае это D[5]. Дорешаем наш пример: D[5]=min(6+20, 5+20, 7+5)=min(26, 25, 12)=12

D[1]	D[2]	D[3]	D[4]	D[5]
5	7	5	6	12 – ответ задачи

Принцип, используемый при решении этой задачи называется динамическим программированием. В данном случае мы решаем полную задачу, постепенно расширяя ее размерность и используя решения более маленьких «подзадач».

 

 

N человек хотят купить билеты. Для каждого известны 3 числа A, B и C - время покупки билета для себя, для себя и следующего, для себя и двух следующих. Требуется купить билеты всем за кратчайшее время.

5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1

12

2
3 4 5
1 1 1

4