Дан треугольник, составленный из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.
Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.
Входные данные:
Первым числом во входном файле с именем INPUT.TXT является количество строк в треугольнике. Пример файла исходных данных представлен ниже.
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Выходные данные:
В выходной файл с именем OUTPUT.TXT записывается только наибольшая сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных выше исходных данных.
7+3+8+7+5=30
Для хранения треугольника заведем массив 100*100 из элементов word, т.к. будет использоваться для передачи суммы в следующую строку. Начнем анализировать треугольник, двигаясь от предпоследней строки к первой (такой тип движения избавит нас от части частных случаев). Итак, смотрим на предпоследнюю строку. У нее по диагонали снизу есть два соседа (в треугольном массиве это число которое находится на 1 клетку ниже и число, на 1 клетку ниже и правее данного) - выберем из них наибольший и прибавим к значению элемента значение наибольшего из нижних соседей. Повторяя эту операцию для каждой строки до вершины и для самой вершины, в вершине (элемент (1;1)) получим искомую сумму. Если бы мы двигались сверху вниз, то возникал бы случай для крайних элементов, у которых всего один сосед.
var inp:array[1..100,1..100] of word;
scount,i,j,row:byte;
f:text;
t,t1,t2:word;
begin
assign(f,'input.txt');
reset(f);
readln(f,scount);
for i:=1 to scount do
for j:=1 to i do begin
read(f, inp[i][j]);
end;
close(f);
row := scount - 1;
while (row > 0) do begin
for j:=1 to row do begin
t:= inp[row][j];
t1:=inp[row+1][j];
t2:=inp[row+1][j+1];
if t1 > t2 then inp[row][j]:=t+t1 else inp[row][j]:=t+t2;
end;
dec(row);
end;
assign(f,'output.txt');
rewrite(f);
write(f,inp[1][1]);
close(f);
end.