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

[Рыженькая]

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

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

[volvo]

To: Рыженькая
Вот тут есть решение твоей задачи полностью, правда на Сях... Разберешься, или перевести на Паскаль?
http://oasis.secna.ru/russian/olymp/acm98/...angster.cpp.htm

[Рыженькая]

на Си я тоже это нашла, но я что в Си, что в Паскале . Я была бы очень признательна, если бы вы помогли перевести

[volvo]

Рыженькая, держи

{
  N - "GANGSTERS"
}

Const
  MaxN = 100;

Var
  f_in, f_out: Text;
  N, K, TT: Integer;
  matr: Array[0 .. Succ(MaxN), 0 .. Succ(MaxN)] of integer;

Procedure GetData;
Var
  i, j: integer;
  T, P, S: Array[0 .. MaxN] Of Integer;
  Flag: Boolean;
  a: integer;
begin
  ReadLn(f_in, N, K, TT);

  T[0] := 0; P[0] := 0; S[0] := 0;
  For i := 1 To N Do Read(f_in, T[i]);
  For i := 1 To N Do Read(f_in, P[i]);
  For i := 1 To N Do Read(f_in, S[i]);

  For i := 1 To Pred(N) Do
    For j := Succ(i) To N Do
      If (T[i] = T[j]) and (S[i] = S[j]) Then Begin
        Inc(P[i], P[j]); P[j] := 0; T[j] := TT+2;
      End;

  Flag := True;
  While Flag Do Begin
    Flag := False;
    for i := 1 To Pred(N) Do
      If T[i] > T[Succ(i)] Then Begin
  	 a:=T[i]; T[i]:=T[i+1]; T[i+1]:=a;
  	 a:=P[i]; P[i]:=P[i+1]; P[i+1]:=a;
  	 a:=S[i]; S[i]:=S[i+1]; S[i+1]:=a;
  	 Flag := False;
      End;
  End;

  For i := N DownTo 1 Do
    If T[i] > TT Then Dec(N);

  For i := 0 To N Do
    For j := 0 To N Do Matr[j, i] := 0;
  For i := 1 To N Do
    For j := 0 To Pred(i) Do
      If (T[i]-T[j]) >= Abs(S[i]-S[j]) Then Matr[j, i] := P[i];

End;


Procedure Solve;
Var
  MaxRes: LongInt;
  i, j: integer;
  res: Array[0 .. succ(MaxN)] Of LongInt;
Begin

  For i := 0 To N Do res[i] := -1;
  res[0] := 0;
  For i := 1 To N Do Begin

    For j := 0 To N Do
      If (res[j] <> -1) and (i <> j) and
         (Matr[j, i] <> 0) and (res[i] < res[j]+Matr[j, i]) Then
        res[i] := res[j]+Matr[j, i];
  End;

  MaxRes := 0;
  For i := 1 To N Do
    If MaxRes < res[i] Then MaxRes := res[i];
  WriteLn(f_out, MaxRes, ' ');
End;


begin
  Assign(f_in, 'gangster.in'); Reset(f_in);
  Assign(f_out, 'gangster.out'); Rewrite(f_out);

  GetData;
  Solve;

  Close(f_out);
  Close(f_in);
end.

Все комментарии я убрал, их смотри по моей ссылке, программа получилась практически 1 в 1, так что это будет просто сделать

[Рыженькая]

Спасибо ооогромное

[Рыженькая]

Если заходить по твоей ссылки, то коментарии к задаче в виде иероглифов, жалко...Может у кого нибудь нормально видно, напишите пожалуйста

[volvo]

Рыженькая, кодировку поменяй на Cyrillic (KOI8-R)

[Guest]

аха, всё получилось, большое спасибо