Заняття (15.03.2017)

Добавил(а) Administrator

21.03.17 10:19

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

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

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

	1	2	3	4	5	6	7	8	9		1	2	3	4	5	6	7	8	9
1	2	1	0	8	4	1	4	9	6	1	2	3	3	12	16	17	20	30	36
2	6	2	5	7	3	2	10	1	3	2	8	10	15	22	25	27	37	37	40
3	2	8	6	6	6	6	8	5	8	3	10	17	24	30	35	41	49	55	62
4	5	9	5	9	6	6	4	6	9	4	15	26	31	41	47	53	57	63	72
5	7	4	6	7	3	5	8	4	1	5	21	30	38	48	51	58	66	71	73
6	2	5	4	9	4	5	5	4	10	6	24	35	41	56	60	66	72	75	85
7	4	3	8	1	0	6	6	9	4	7	28	39	49	58	61	71	77	87	91
8	4	3	7	8	8	9	5	9	1	8	32	42	57	65	74	83	89	98	99
9	2	5	2	2	2	1	6	7	6	9	34	47	59	68	76	84	95	105	110
10	10	1	6	2	10	7	4	5	3	10	44	48	65	69	86	93	99	110	113

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

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

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

Ім'я файлу програми:	Bilet.*
Ім'я вхідного файлу:	Bilet.dat
Ім'я вихідного файлу:	Bilet.dat
Максимальний час роботи на одному тесті:	5 секунд
Максимальна оцінка за завдання:	100 балів

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

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

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

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

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

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

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

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

Приклади

Bilet.dat

Bilet.sol

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

3 4 5

1 1 1

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[i]= min ( D[i-1]+A_i, D[i-2]+ B_i-1, D[i-3]+ C_i-2 )

D[1]	D[2]	D[3]	D[4]	D[5]
5	7	5	6	12 - відповідь завдання

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