program TW APPTYPE CONSOLE uses SysUtils var Arr array of array of Int

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
program TW;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
Arr: array of array of Integer; // Собсна сам треугольник
I,J: Integer; // понятно даже морковке..
Sz: Integer; // размер массива
Sum, MaxSum: Integer; // Текущая Сумма пути и макс сумма
CurN: Integer; // Текущий элемент суммирования
// !!! Битовые вектора, извращенцы погут заменить их на Массивы т. булен
CurWay: Integer; // Текущий путь
MaxWay: Integer; // Максимальный найденный путь
// ЗЫ: из надо делать ансайнт, но как это пишется на дельфе не помню...
begin
// ввод
Write('Enter size of Triangle: ');
Readln(Sz);
setlength(Arr,Sz);
// ввод матрицы
writeln('Enter Matrix');
for I:=0 to Sz-1 do
begin
SetLength(Arr[I],I+1);
for J:=0 to I do
Read(Arr[I][J]);
end;
// !!! Работает тока, если есть хотяб одна послед. с положительной суммой
MaxSum:=0;
// умный цикл, перебирающий все пути... понять можно, если напрячь моск...
for CurWay:=0 to (1 shl (sz-1) -1) do
begin
Sum:= 0;// полное аппнуления... а я пронега-сцуго забыл
CurN:=0;
for I:=0 to Sz-1 do // Подсчёт текущей суммы
begin
Sum:= Sum+Arr[I][CurN]; // Хорошо бы избавиться от полного перещёта суммы
// в части случаев
// Дети, не пугайтесь... так мы просто достаём (Сз-И)-й элемент
// битового вектора (если считать с единицы, с конца)...
if(((CurWay shr (Sz-I-2))and 1)=1) then
CurN:=CurN+1; // 1 в БВ означает, что мы идём вправо...
end;
if(Sum>MaxSum)then
begin
MaxSum:=Sum;
MaxWay:=CurWay;
end;
end;
// Расшифровка и вывод результатов...
for I:=0 to sz-2 do
begin
if(((MaxWay shr (Sz-I-2))and 1)=1) then
Write('R ')
else
Write('D ');
end;
Readln; Readln;
end.