6. Динамическое программирование

Разбор задачи 584. Broken Sword: потерянный файл

uses math;
const inf=1000000;
var n,i,j,k,r:integer;
  a:array[1..1001] of integer; { количество ящиков в i-м штабеле }
  t:array[0..1001,0..100] of integer;
    { таблица для динамического программирования -
      количество ящиков, которые нужно переместить, 
      чтобы оказаться i-м штабеле на высоте j }
begin
  read(n);
  for i:=1 to n do
    read(a[i]);
  for j:=1 to 100 do
    t[0,j]:=inf; { нельзя сделать выше начальную клетку }
  for i:=1 to n+1 do
    for j:=0 to 100 do { проверяем все высоты }
    begin
      r:=inf;
      for k:=max(0,j-2) to min(100,j+2) do 
        { проверяем все достижимые с высоты j }
        r:=min(r,t[i-1,k]); { находим минимум }
      t[i,j]:=r+abs(a[i]-j); { минимум + количество ящиков,
         которые нужно добавить/убрать для получения высоты j }
    end;
  writeln(t[n+1,0]);
end.