"Гангстеры", олимпиадная задача Опции

[Рыженькая]

Помогите пожалуйста с задачкой, нужно для курсовика.

N гангстеров собираются в ресторан, i-й гангстер приходит в момент времени Ti, богатство этого гангстера Pi. Дверь ресторана имеет К+1 степень открытости, они обозначаются целыми числами из интервала [0,К]. Степень открытости двери может изменяться на единицу за единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же положении в котором и была. В начальный момент времени дверь закрыта (положение 0). i-й заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0,Т]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.
Ограничения: 1<=N<=100, 1<=T<=30 000, 0<=Ti<=T, 1<=Pi<=300, 1<=Si<=K, все числа целые, время 2 с.
Ввод из файла gangster.out. Вывести 1 число- максимальное суммарное богатство гангстеров, попавших в ресторан. Если зайти не удалось никому, вывести 0.

Примеры
Ввод1_____ Ввод2
4_ 10_ 20 _____ 2 _ 17 _ 100
10_16_ 8_16 _____ 5 _ 0
10_11_15_1______ 50 _ 33
10_ 7_1_8 ______ 6 _ 1

Ввод1_____Ввод2
26 _____ 0

________________________________________________

в интернете смогла найти примерное решение одной из процедур, но так как в Паскале я тю тю, очень прошу помочь сделать полностью

Данные

Исходный код

Const MaxN=500;
MaxK=100;
Var N,K,Tend:Integer;
S,P,T:Array[0..MaxN] Of Integer;
Основная программа
Begin
Init;
Solve;
Done;
End.
Приведем только процедуру Solve, остальные достаточно очевидны.
Procedure Solve;
Var i,j:Integer;
SOld,SNew:Array[0..MaxK] Of LongInt;
{массивы для формирования оценок вершин решетки}
Begin
SOld[0]:=0;
For i:=1 To K Do SOld[i]:=-MaxLongInt;
SNew:=SOld;
For i:=1 To Tend Do Begin
{цикл по моментам времени}
SNew[0]:=SOld[0];
For j:=1 To i Do
{цикл по достижимым состояниям решетки}
SNew[j]:=Max(SOld[j-1],SOld[j]);
{реализация функции Max очевидна}
{формирование оценок вершин решетки}
For j:=1 To N Do {цикл по посетителям}
If (T[j]=i) And (SNew[S[j]]<>-MaxLongInt)
{если время прихода посетителя совпадает
с рассматриваемым моментом времени
и состояние достижимо, то изменяем
оценку вершины, соответствующей полноте
посетителя}
Then Inc(SNew[S[j]],P[j]);
SOld:=SNew;{запоминаем массив оценок}
End;
Res:=-MaxLongInt;
For i:=1 To K Do Res:=Max(Res,SNew[i]);
{находим максимальное значение
в окончательном массиве оценок}
End;

Сообщение отредактировано: Altair - 21.11.2005 23:37