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.