记录编号	24724	评测结果	AWWAAAWAAA
题目名称	[USACO Jan09] 气象牛	最终得分	70
用户昵称	reamb	是否通过	未通过
代码语言	Pascal	运行时间	0.017 s
提交时间	2011-04-15 18:09:20	内存使用	0.19 MiB

program qixiangniu;
var
  f,sum:array[1..100,1..100]of longint;
  q,a:array[1..100]of longint;
  n,e,i,j,k,min,min1,min2:longint;
begin
  assign (input,'baric.in');
  reset (input);
  assign (output,'baric.out');
  rewrite (output);
    readln (n,e);
    for i:=1 to n do
      readln (a[i]);
    for i:=1 to n do
      for j:=i to n do
        for k:=i+1 to j-1 do
          sum[i,j]:=sum[i,j]+abs(2*a[k]-a[i]-a[j]);
    q[n]:=0;
    for i:=n-1 downto 1 do
      for j:=i+1 to n do
        q[i]:=q[i]+2*abs(a[j]-a[i]);
    f[1,1]:=0;
    for i:=2 to n do
      for j:=1 to i-1 do
      f[i,1]:=f[i,1]+2*abs(a[i]-a[j]);
    for i:=2 to n do
    begin
      for j:=2 to i do
      begin
        min:=maxlongint;
        for k:=j-1 to i-1 do
          if (f[k,j-1]+sum[k,i]<min) then
            min:=f[k,j-1]+sum[k,i];
        f[i,j]:=min
      end
    end;
    min1:=maxlongint;
    min2:=maxlongint;
    for i:=1 to n do
      for j:=1 to i do
        if f[i,j]+q[i]<=e then
        begin
          if j<min1 then
          begin
            min1:=j;
            min2:=f[i,j]+q[i]
          end;
          if min1=j then
            if f[i,j]+q[i]<min2 then
              min2:=f[i,j]+min2
        end;
  writeln (min1,' ',min2);
  close (input);
  close (output)
end.