Решение

Тема: динамическое программирование
Сложность: высокая

Вычисление производится методом динамического программирования. Элемент матрицы `T[i,j]` содержит минимальную стоимость для проведения дороги в позицию после `i`-го участка горного рельефа на высоту `j`. `T[0,j]` вычисляется как `j^2*C_2/2`, так как попасть на высоту `j` можно только построив насыпь.

При вычислении `T[i,j]` возможны три случая.

A. Если высота `i`-го участка рельефа выше `j`, то попасть в эту точку можно только с помощью прокладки туннеля: `T[i,j]=T[i-1,j]+C_1`.

B. Если высота `i`-го участка рельефа равна `j`, то попасть в эту точку можно либо проведя дорогу по поверхности горы, либо построив наклонную насыпь с большей высоты: `T[i,j]=min(T[i-1,j],T[i-1,j+1]+C_2/2)`.

C. Если высота `i`-го участка рельефа меньше `j`, то попасть в эту точку можно либо построив наклонную насыпь с большей или меньшей высоты, либо построив v-образную дорогу (насыпать дорогу горизонтально нет смысла), либо построить мост, если возможно (далее на высоте j должна быть скала для правой опоры моста, и не более чем в 3 единицах должна быть скала для левой опоры моста). `T[i,j]=min(\ min(T[i-1,j]-C_2/4,T[i-1,j+1]+C_2/2,T[i-1,j-1]-C_2/2)\ +\ (j-h[i])*C_2,\ "вариант"\ с\ "мостом")`.

После заполнения матрицы нужно найти минимум среди значений `T[n,j]+\ j^2*C_2/2`.

var N,i,j,k,c1,c2,c3:integer;
  h:array[1..1000] of integer;
  t:array[0..1000,0..1000] of extended;
  r:extended;
procedure setmin(v:extended);
begin
  if v<t[i,j] then t[i,j]:=v;
end;
begin
  read(n,c1,c2,c3);
  for i:=1 to n do
    read(h[i]);
  for j:=0 to 1000 do
    t[0,j]:=j*j/2*c2;
  for i:=1 to n do
    for j:=0 to 1000 do
    begin
      if h[i]>j then
        t[i,j]:=t[i-1,j]+c1
      else if h[i]=j then
      begin
        t[i,j]:=t[i-1,j];
        if j<1000 then setmin(t[i-1,j+1]+c2/2);
      end
      else
      begin
        t[i,j]:=t[i-1,j]+(j-h[i])*c2-c2/4;
        if j<1000 then setmin(t[i-1,j+1]+(j-h[i])*c2+c2/2);
        setmin(t[i-1,j-1]+(j-h[i])*c2-c2/2);
        if (i<n) and (h[i+1]>=j) then
        begin
          for k:=1 to 3 do
            if (i>k) and (h[i-k]>=j) then
            begin
              setmin(t[i-k,j]+k*c3);
              break;
            end;
        end;
      end;
    end;
  r:=t[n,0];
  for j:=1 to 1000 do
    if r>t[n,j]+j*j/2*c2 then
      r:=t[n,j]+j*j/2*c2;
  writeln(r:1:2);
end.