记录编号	32587	评测结果	AAAAAAAAAA
题目名称	608.删数	最终得分	100
用户昵称	lizhe	是否通过	通过
代码语言	Pascal	运行时间	0.013 s
提交时间	2011-11-07 14:11:46	内存使用	0.19 MiB

program remove;
var
  i,j,k,k1,k2,n:longint;
  f,w:array[0..100,0..100]of longint;
  a:array[1..100]of longint;
procedure init;
begin
  assign(input,'remove.in');
  reset(input);
  assign(output,'remove.out');
  rewrite(output);
  read(n);
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n do
    f[i,1]:=a[i];
  for i:=1 to n do
    for j:=1 to n do
      if i<=j then
      begin
        w[i,j]:=abs(a[i]-a[j])*(j-i+1);
        if i=j then
          w[i,j]:=a[i]
      end
end;

procedure dp;
begin
  for j:=1 to n do
    for i:=1 to n do
      if i+j-1<=n then
      begin
        f[i,j]:=w[i,i+j-1];
        for k:=i to i+j-1 do
          if f[i,j]<f[i,k-i+1]+f[k+1,j-(k-i+1)] then
            f[i,j]:=f[i,k-i+1]+f[k+1,j-(k-i+1)]
      end
end;

procedure print;
begin
  writeln(f[1,n]);
  close(input);
  close(output)
end;

begin
  init;
  dp;
  print
end.