记录编号	24811	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 气象牛	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	0.048 s
提交时间	2011-04-28 11:59:18	内存使用	8.89 MiB

const
  oo=maxlongint;

var
  n,e:longint;
  a,after,before:Array[0..100000]of longint;
  f,sum:array[0..999,0..999]of longint;

procedure init;
var
  i,j,k:longint;
begin
  assign(input,'baric.in'); reset(input);
  assign(output,'baric.out'); rewrite(output);
  readln(n,e);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do
  begin
    for j:=i+1 to n do
    inc(after[i],2*abs(a[j]-a[i]));

    for j:=1 to i-1 do
    inc(before[i],2*abs(a[j]-a[i]));
  end;

  for i:=1 to n-1 do
   for j:=i+1 to n do
   begin
     for k:=i+1 to j-1 do
     inc(sum[i,j],abs(2*a[k]-a[i]-a[j]));
   end;
end;

procedure dp;
var
  i,j,k,min,now:longint;
begin
  for i:=1 to n do f[i,1]:=before[i]+after[i];

  for j:=2 to n do
   for i:=j to n do
   begin
     min:=oo;
     for k:=j-1 to i-1 do
     begin
       now:=f[k,j-1]-after[k]+after[i]+sum[k,i];
       if now<min then min:=now;
     end;
     f[i,j]:=min;
   end;
end;

procedure print;
var
  p,i,j,min:longint;
begin
  p:=oo;

  for j:=1 to n do
   for i:=j to n do
   if (f[i,j]<=e)and(j<p) then
   begin
     p:=j;
     break;
   end;
  write(p,' ');

  min:=oo;
  for i:=p to n do
  if f[i,p]<min then min:=f[i,p];
  writeln(min);

  close(input);
  close(output);
end;

begin
  init;
  dp;
  print;
end.