记录编号	148139	评测结果	AAAAAAAAAA
题目名称	[NOI 1999]棋盘分割	最终得分	100
用户昵称	hjt	是否通过	通过
代码语言	Pascal	运行时间	0.016 s
提交时间	2015-02-07 14:48:07	内存使用	0.97 MiB

program division;
const max=1000000000000;
var i,j,k,l,m,n:Longint;
    ave:real;
    s,a:array[0..8,0..8]of real;
    d:array[0..15,0..8,0..8,0..8,0..8]of real;

function min(x,y:real):real;
begin
  if x<y then exit(x)
  else exit(y);
end;

function dp(k,xx,yy,x,y:longint):real;
var l,m:longint;t:real;
begin
  if d[k,xx,yy,x,y]<>max then exit(d[k,xx,yy,x,y]);
  if k=0 then
    begin
      t:=sqr(s[x,y]-s[x,yy-1]-s[xx-1,y]+s[xx-1,yy-1]);
      d[k,xx,yy,x,y]:=t;
      exit(d[k,xx,yy,x,y]);
    end;
  t:=max;
  for l:=xx to x-1 do
    for m:=0 to k-1 do
    begin
      t:=min(t,dp(k-1-m,xx,yy,l,y)+dp(m,l+1,yy,x,y));
      //t:=min(t,dp(m,l+1,yy,x,y)+dp(k-1-m,xx,yy,l,y));
    end;
  for l:=yy to y-1 do
    for m:=0 to k-1 do
    begin
      t:=min(t,dp(k-1-m,xx,yy,x,l)+dp(m,xx,l+1,x,y));
      //t:=min(t,dp(m,xx,l+1,x,y)+dp(k-1-m,xx,yy,x,l));
    end;
  d[k,xx,yy,x,y]:=t;
  exit(d[k,xx,yy,x,y]);
end;

procedure fill;
begin
  for i:=1 to 8 do
    for j:=1 to 8 do
      for l:=1 to 8 do
        for m:=1 to 8 do
          for k:=0 to n do
            d[k,i,j,l,m]:=max;
end;

procedure cal;
begin
  for i:=1 to 8 do
    for j:=1 to 8 do
      s[i,j]:=s[i-1,j]+s[i,j-1]+a[i,j]-s[i-1,j-1];
end;

begin
  assign(input,'division.in');
  assign(output,'division.out');
  reset(input);
  rewrite(output);
  readln(n);
  fill;
  for i:=1 to 8 do
    for j:=1 to 8 do
      read(a[i,j]);
  cal;
  ave:=s[8,8]/n;
  writeln(sqrt(dp(n-1,1,1,8,8)/n-sqr(ave)):0:3);
  close(input);
  close(output);
end.