学步园

【题意】

有n块高低不同的地面，每让一块高度改变1则需支付1的代价，问将地面高度变为不上升或不下降序列所需最小代价

【输入】

第一行一个n

接下来n行每行一个数字表示该块地面的高度

【输出】

一个数字，表示最小代价

离散高度后dp

用f[i][j]表示考虑钱i块地面，当前地面高度离散后为j的所需最小代价

f[i][j]=min(f[i-1][k]+abs(h[i]-num[j]))(若为上升序列则k<=j，若为下降序列则k>=j)

枚举k比较慢所以预处理一下

由于f[i]的取值只跟f[i-1]有关，所以运用滚动数字

program poj3666;
var
  n,i,j,k,tot,o,ans:longint;
  h,dl,num,min:array [0..2001] of longint;
  f:array [0..1,0..2001] of longint;

procedure swap (var a,b:longint);
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure qsort (s,e:longint);
var
  i,j,k:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=dl[(s+e) div 2];
  while i<=j do
    begin
      while dl[i]<k do inc(i);
      while dl[j]>k do dec(j);
      if i>j then break;
      swap(dl[i],dl[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

begin
  read(n);
  for i:=1 to n do
    read(h[i]);
  for i:=1 to n do
    dl[i]:=h[i];
  qsort(1,n);
  k:=0;
  dl[0]:=-maxlongint;
  for i:=1 to n do
    if dl[i]<>dl[k] then
      begin
        inc(tot);
        num[tot]:=dl[i];
        k:=i;
      end;
  ans:=maxlongint;
  fillchar(f,sizeof(f),0);
  o:=0;
  for i:=1 to n do
    begin
      o:=1-o;
      min[0]:=maxlongint;
      for j:=1 to tot do
        begin
          min[j]:=min[j-1];
          if f[1-o,j]<min[j] then min[j]:=f[1-o,j];
        end;
      for j:=1 to tot do
        f[o,j]:=min[j]+abs(h[i]-num[j]);
    end;
  for i:=1 to tot do
    if f[o,i]<ans then ans:=f[o,i];
  fillchar(f,sizeof(f),0);
  o:=0;
  for i:=1 to n do
    begin
      o:=1-o;
      min[tot+1]:=maxlongint;
      for j:=tot downto 1 do
        begin
          min[j]:=min[j+1];
          if f[1-o,j]<min[j] then min[j]:=f[1-o,j];
        end;
      for j:=1 to tot do
        f[o,j]:=min[j]+abs(h[i]-num[j]);
    end;
  for i:=1 to tot do
    if f[o,i]<ans then ans:=f[o,i];
  writeln(ans);
end.