Билеты на мюзикл

[hewlett]

За билетами на премьеру нового мюзикла собралась очередь из N лиц, каждое из которых хочет купить 1 билет. На всю очередь работала только одна касса, потому продажа билетов продвигалась очень медленно, от чего «клиенты» очереди впадали в отчаяние. Самые сообразительные быстро приметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким людям, которые стоят рядом, отдавать деньги первому из них, чтобы он купил билеты на всех.
Но для борьбы со спекулянтами кассир продавала не больше 3-х билетов в одни руки, потому договориться таким образом между собой могли лишь 2 или 3 лица, которые стоят рядом.
Известно, что на продажу і лицу из очереди одного билета кассир тратит Аі секунд, на продажу двух билетов – Ві секунд, трёх билетов – Сi секунд.
Задание. Напишите программу, которая определит минимальное время, за которое можно было бы обслужить всех покупателей.
Обратите внимание, что билеты на группу людей, которые объединились, всегда покупает первый из них. Также никто с целью ускорения не покупает лишние билеты (то есть билеты, которые никому не нужные).
Входные данные. Первая строка входного файла содержит единственное число N – количество покупателей в очереди (1N5000). В каждой из следующих N строк записана тройка натуральных чисел Аі, Bi, Сi. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы
Выходные данные. Исходный файл содержит одно число – минимальное время в секундах, за которое можно было бы обслужить всех покупателей.
Пример входных и выходных данных

 Input.txt  Output.txt 
 5                  12 
 5 10 15 
 2 10 15 
 5 5 5 
 20 20 1 
 20 1 1 

 Input.txt  Output.txt 
 2                  4 
 3 4 5 
 1 1 1

[Utkin]

Берешь целое от деления на три всех покупателей. Умножаешь на Ci - это общая масса людей, допустим Х. Затем берешь остаток от деления на три всех покупателей. Это будет либо 0, либо 1, либо 2. Соответственно если нуль, то ответ Х. Если 1 то Х+Ai, если 2 то X+Bi

[Serge_Bliznykov]

Сообщение от Utkin

Умножаешь на Ci -

а ничего, что Ci для каждой тройки людей разное?!

А во-вторых, алгоритм КАТЕГОРИЧЕСКИ не подходит!
потому как времея покупки одного (или двух) билетов может оказаться (как в примере 1) меньше, чем время покупки трёх билетов. Разберите пример номер 1

тут в цикле нужно брать тройку чисел и для неё находить минимальное время обработки. Потом, увеличивать индекс на число купленных билетов и повторять цикл.

[s-andriano]

Сообщение от Serge_Bliznykov

тут в цикле нужно брать тройку чисел и для неё находить минимальное время обработки. Потом, увеличивать индекс на число купленных билетов и повторять цикл.

Что-то мне кажется, эта задача вообще не решается линейным алгоритмом.
Рекурсия до исчерпания очереди. На каждом шаге рекурсии ветвление на 3 - по возможном количеству билетов, проданных данному покупателю.

[Utkin]

а ничего, что Ci для каждой тройки людей разное?!

Когда я читал задание это было непонятно так как образцы файлов не были отформатированы нужным образом . Если людей много пусть берет усредненную Ci

[s-andriano]

Сообщение от Utkin

Если людей много пусть берет усредненную Ci

1. Только стандартных методов нахождения среднего, минимум, четыре (арифметическое, геометрическое, гармоническое и медиана).
2. Обычно задачи на оптимизация требуют как раз нахождения решения более оптимального, чем в среднем.

[Serge_Bliznykov]

про среднее значение - это была "утка"-шутка

а автор темы, наверное, молчит, потому что он получил решение на другом форуме - вот
позволю себе процитировать чужое решение
(с) valeriikozlov
простое дп:

var n,i,a,b,c:longint;
mas:array[0..5002] of longint;
begin
 readln(n);
 mas[0] := 0;
 for i:=1 to n+2 do
   mas[i]:=20000000;
 for i:=1 to n do begin
   readln(a,b,c);
   if mas[i]>a+mas[i-1] then mas[i]:=a+mas[i-1];
   if mas[i+1]>b+mas[i-1] then mas[i+1]:=b+mas[i-1];
   if mas[i+2]>c+mas[i-1] then mas[i+2]:=c+mas[i-1];
 end;
 writeln(mas[n]);
end.