比赛 NOIP_3 评测结果 AWWWWWAWWA
题目名称 棋盘分割 最终得分 30
用户昵称 lc 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-09-12 22:06:56
显示代码纯文本
program day3_1;
 var
     ave:real;
     a:array[0..8,0..8] of longint;
     f:array[0..15,1..8,1..8,1..8,1..8] of real;
     n:integer;

 procedure init;
  var
      i,j:integer;
 begin
  read(n);
  for i:=1 to 8 do
   for j:=1 to 8 do
   begin
   read(a[i,j]);
   a[i,j]:=a[i-1,j]+a[i,j-1]-a[i-1,j-1]+a[i,j];
   end;
  ave:=a[8,8]/n;
 end;

 function Suan(x1,y1,x2,y2:integer):longint;
  begin
   exit(a[x2,y2]-a[x1-1,y2]-a[x2,y1-1]+a[x1-1,y1-1]);
  end;

 procedure main;
  var
      tmp,min:real;
      i,x1,y1,x2,y2,k:integer;
  begin
   for x1:=1 to 8 do
    for y1:=1 to 8 do
     for x2:=x1 to 8 do
      for y2:=y1 to 8 do
      f[1,x1,y1,x2,y2]:=sqr(a[x2,y2]-a[x1-1,y2]-a[x2,y1-1]+a[x1-1,y1-1]-ave);

   for i:=2 to n do
    for x1:=1 to 8 do
     for y1:=1 to 8 do
      for x2:=1 to 8 do
       for y2:=1 to 8 do
       begin
       min:=1e30;

        for k:=x1 to x2-1 do
         begin
         tmp:=sqr(Suan(x1,y1,x2,k)-ave)+
         f[i-1,x1,k+1,x2,y2];
         if tmp<min
         then min:=tmp;
         end;

        for k:=y1 to y2-1 do
         begin
         tmp:=sqr(Suan(x1,y1,k,y2)-ave)+
         f[i-1,k+1,y1,x2,y2];
         if tmp<min
         then min:=tmp;
         end;
        f[i,x1,y1,x2,y2]:=min;
       end;

  writeln(sqrt( f[n,1,1,8,8]/n ):0:3);
 end;

 begin
  assign(input,'division.in');
  assign(output,'division.out');
  reset(input); rewrite(output);
  init;
  main;
  close(input); close(output);
 end.