Сайт підготовки до олімпіади з інформатики

Мишка і зернинки

https://www.e-olymp.com/uk/problems/15

Задача 4 «Зернинки»

Мишка збирає зернинки на шаховій дошці. Може рухатись вниз та вліво. Зібрати найбільше зернинок.

=МАКС(C3+M3;C3+N2)

Задачі 6. Купування квитків

https://www.e-olymp.com/uk/problems/799

За квитками на прем'єру нового мюзиклу вишикувалася черга з N людей, кожний з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків йшов дуже повільно, приводячи людей черги у відчай. Найкмітливіші швидко відмітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці ж квитки продаються поодинці. Тому вони запропонували декільком людям, які стоять підряд віддавати гроші першому з них, щоб він купив квитки на всіх.

Проте для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 підряд вартих людини.

Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків - Bi секунд, трьох квитків - Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути продані квитки для всіх людей черги.

Зверніть увагу, що квитки на групу людей, що об'єдналися, завжди купує перший з них. Також ніхто в цілях прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).

Формат вхідних даних

У вхідному файлі записано спочатку число N - кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел Ai_, Bi_, Ci_. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

Формат вихідних даних

У вихідний файл виведіть одне число - мінімальний час в секундах, за яке могли бути обслужені всі покупці.

Приклади

N=5

D[i]= min ( D[i-1]+A_i,  D[i-2]+ B_i-1,  D[i-3]+ C_i-2 )

d[0]= 0;

d[1]= а[1];

d[2]= min(а[1]+a[2], b[1]);

for (i=3;i<=n;i++)  d[i]= min( d[i-1]+ а[i], min( d[i-2]+ b[i-1], d[i-3]+ c[i-2]));