BARIC - Bò Ba-ri

Tác giả: RR

Ngôn ngữ: Pascal

{
PROG: baric
LANG: PASCAL
ID: invinci3
}
const
  FINP='';
  FOUT='';
  MAXN=101;
  oo=1000000000;
var
  f1,f2:text;
  e,n,kq:longint;
  nn,m:array[1..MAXN] of longint;
  d,sum:array[1..MAXN,1..MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n,e);
  for i:=1 to n do read(f1,m[i]);
end;
procedure init;
var
  i,j,k:longint;
begin
  for i:=1 to n-2 do
  for j:=i+2 to n do
    for k:=i+1 to j-1 do
      inc(sum[i,j],abs(2*m[k]-m[i]-m[j]));
end;
procedure solve;
var
  i,j,k,x:longint;
begin
  for i:=1 to n do
  for j:=2 to n do
    d[i,j]:=oo;
  for k:=1 to n do
    nn[k]:=oo;
  for i:=1 to n do
    begin
      d[i,1]:=0;
      for j:=1 to i-1 do
        inc(d[i,1],2*abs(m[j]-m[i]));
      x:=d[i,1];
      for j:=i+1 to n do inc(x,2*abs(m[j]-m[i]));
      nn[1]:=min(nn[1],x);
    end;
  for i:=2 to n do
  for k:=2 to i do
    begin
      for j:=1 to i-1 do
        d[i,k]:=min(d[i,k],d[j,k-1]+sum[j,i]);
      x:=d[i,k];
      for j:=i+1 to n do inc(x,2*abs(m[j]-m[i]));
      nn[k]:=min(nn[k],x);
    end;
end;
procedure ans;
var
  k:longint;
begin
  for k:=1 to n do
    if nn[k]<=e then
      begin
        writeln(f2,k,' ',nn[k]);
        exit;
      end;
end;
begin
  openF;
  inp;
  init;
  solve;
  ans;
  closeF;
end.

Download