Динамическое программирование. Лесенка - Free Pascal

Формулировка задачи:

Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Также он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошел Вова. Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму. Входные данные Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество ступеней лестницы. Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Количество ступеней не превышает 1000, числа, написанные на ступенях, не превосходят по модулю 1000. Выходные данные Выходной файл OUTPUT.TXT должен содержать в первой строке наибольшее значение суммы. Во второй строке должны быть записаны через пробел номера ступеней по возрастанию, по которым должен шагать Вова. ссылка

var x1,y1,x2,y2:longint;
st,i,x,a,y:longint;
mas,p,d:array[-2..2000] of longint;
 
begin
 assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);

read (x);
for i:=1 to x do
read (d[i]);
d[0]:=0;
d[-1]:=100000000;
for i:=2 to x do
if d[i-1]> d[i-2] then begin
 d[i]:=d[i-1]+d[i];p[i]:=i-1;
 end else  begin
 d[i]:=d[i-2]+d[i];p[i]:=i-2;
 end;
writeln (d[x]);
 
  while p[i]<>0 do
    begin
    inc(st);mas[st]:=p[i];i:=p[i];
    end;
 
for i:=st downto 1 do
 write (mas[i], ' ');
write (x);
end.

можете сказать почему ва 1 тест

Решение задачи: «Динамическое программирование. Лесенка»

Листинг программы

var a, d, way: array [0..1001] of longint;
    i, n: longint;
 
 
 
procedure OutWay (n: longint);
begin
 
 if (way[n] = 0) then
  begin
   write (n,' ');
   exit;
  end;
 OutWay (way[n]);
 write (n,' ');
end;
 
 
 
begin
assign (input,'input.txt'); reset (input);
assign (output,'output.txt'); rewrite (output);
read (n);
 
for i:= 1 to n do
 read (a[i]);
 
 
d[1]:= a[1];
 
for i:= 2 to n do
 if d[i-1] > d[i-2] then
  begin
   d[i]:= d[i-1] + a[i];
   way [i]:= i-1;
  end
 
 else
  begin
   d[i]:= d[i-2] + a[i];
   way [i]:= i-2;
  end;
 
 
 
writeln (d[n]);
OutWay (n);
 
end.

Объяснение кода листинга программы

В данном коде реализуется алгоритм динамического программирования для задачи Лесенка.

В начале кода объявляются массивы a, d, way, а также переменные i, n.
В процедуре OutWay происходит обход пути в обратном порядке. Если значение way[n] равно 0, то это означает достижение конца пути, и число n выводится на экран. В противном случае, рекурсивно вызывается процедура OutWay для значения way[n]. После чего число n выводится на экран.
В основном блоке кода считывается из файла input.txt количество заданий (n).
Затем считываются значения a[i] для каждого i от 1 до n.
Для каждого i от 1 до n-1 формируется значение d[i] на основе значений a[i], a[i-1] и a[i-2]. Если d[i-1] > d[i-2], то d[i] = d[i-1] + a[i], way[i] = i-1. В противном случае, d[i] = d[i-2] + a[i], way[i] = i-2.
В конце кода выводится на экран значение d[n] и вызывается процедура OutWay для n.
Код сохраняет результаты в файл output.txt.