Помогите пожалуйста с задачкой, нужно для курсовика.
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
________________________________________________
в интернете смогла найти примерное решение одной из процедур, но так как в Паскале я тю тю, очень прошу помочь сделать полностью
Данные
To: Рыженькая
Вот тут есть решение твоей задачи полностью, правда на Сях... Разберешься, или перевести на Паскаль?
http://oasis.secna.ru/russian/olymp/acm98/solution/gangster/gangster.cpp.htm
на Си я тоже это нашла, но я что в Си, что в Паскале . Я была бы очень признательна, если бы вы помогли перевести
Рыженькая, держи
{
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.
Спасибо ооогромное
Если заходить по твоей ссылки, то коментарии к задаче в виде иероглифов, жалко...Может у кого нибудь нормально видно, напишите пожалуйста
Рыженькая, кодировку поменяй на Cyrillic (KOI8-R)
аха, всё получилось, большое спасибо