Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ "Гангстеры"

Автор: Рыженькая 22.11.2005 2:34

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

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

________________________________________________


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

Данные

Исходный код
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;

Автор: volvo 22.11.2005 3:31

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

Автор: Рыженькая 22.11.2005 3:45

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

Автор: volvo 22.11.2005 4:10

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

{
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, так что это будет просто сделать smile.gif

Автор: Рыженькая 23.11.2005 1:02

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

Автор: Рыженькая 23.11.2005 23:49

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

Автор: volvo 23.11.2005 23:57

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

Автор: Guest 24.11.2005 17:31

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