记录编号	4792	评测结果	AAAAAAAAAW
题目名称	[NOI 1999]棋盘分割	最终得分	90
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	0.035 s
提交时间	2008-10-22 20:10:49	内存使用	0.55 MiB

program cch(input,output);
const
 maxf=1000000000;
var
 data:array[1..8,1..8] of integer;
 tot,i,j,x1,x2,y1,y2,k,q,n,p:integer;
 x0,ans:real;
 f:array[1..8,1..8,1..8,1..8,0..15] of real;
begin
 assign(input,'division.in');
 assign(output,'division.out');
 reset(input);
 rewrite(output);
 readln(n);
 for i:=1 to 8 do
  for j:=1 to 8 do
   read(data[i,j]);
 for i:=1 to 8 do
  for j:=1 to 8 do inc(tot,data[i,j]);
 x0:=tot/n;
 for x1:=1 to 8 do
  for x2:=x1 to 8 do
   for y1:=1 to 8 do
    for y2:=y1 to 8 do
     begin
      f[x1,x2,y1,y2,0]:=0;
      for k:=x1 to x2 do
       for q:=y1 to y2 do
        f[x1,x2,y1,y2,0]:=f[x1,x2,y1,y2,0]+data[k,q];
      f[x1,x2,y1,y2,0]:=sqr(f[x1,x2,y1,y2,0]-x0);
     end;
 for k:=1 to n-1 do
  for x1:=1 to 8 do
   for x2:=x1 to 8 do
    for y1:=1 to 8 do
     for y2:=y1 to 8 do
      begin
       f[x1,x2,y1,y2,k]:=maxf;
       for q:=x1 to x2-1 do
        for p:=0 to k-1 do
         if f[x1,x2,y1,y2,k]>(f[x1,q,y1,y2,p]+f[q+1,x2,y1,y2,k-1-p]) then
          f[x1,x2,y1,y2,k]:=f[x1,q,y1,y2,p]+f[q+1,x2,y1,y2,k-p-1];
       for q:=y1 to y2-1 do
        for p:=0 to k-1 do
        if f[x1,x2,y1,y2,k]>(f[x1,x2,y1,q,p]+f[x1,x2,q+1,y2,k-p-1]) then
         f[x1,x2,y1,y2,k]:=f[x1,x2,y1,q,p]+f[x1,x2,q+1,y2,k-p-1];
      end;
 ans:=sqrt(f[1,8,1,8,n-1]/n);
 write(ans:0:3);
 close(input);
 close(output);
end.