比赛 NOIP_3 评测结果 C
题目名称 棋盘分割 最终得分 0
用户昵称 0彼岸0 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-09-12 21:10:12
显示代码纯文本
program division;
const fin='division.in'; fout='division.out'; m=8;
var a:array[1..m,1..m] of integer;
    s:array[0..m,0..m] of int;
    f:array[0..15,1..m,1..m,1..m,1..m] of int;
    n,i,j,x,y,x1,y1,x2,y2,k:integer;
    xx:double;
function sum(x1,y1,x2,y2:integer):int;
begin
    sum:=s[x2,y2]+s[x1-1,y1-1]-s[x1-1,y2]-s[x2,y1-1];
    sum:=sum*sum;
end;
function min(a,b:int):int;
begin
    min:=a;if b<min then min:=b;
end;
begin
assign(input,fin); reset(input);
readln(n);
xx:=0;
for i:=1 to m do
    for j:=1 to m do
      begin
        read(a[i,j]);
        xx:=xx+a[i,j];
      end;
xx:=xx*xx/(n*n);
close(input);
fillchar(s,sizeof(s),0);
for i:=1 to m do
    begin
      k:=0;
      for j:=1 to m do
        begin
          k:=k+a[i,j];
          s[i,j]:=s[i-1,j]+k;
        end;
    end;
fillchar(f,sizeof(f),$7f);
for x1:=1 to m do
    for y1:=1 to m do
      for x2:= x1 to m do
        for y2:=y1 to m do
          f[0,x1,y1,x2,y2]:=sum(x1,y1,x2,y2);
for k:=1 to n-1 do
    for x1:=1 to m do
      for y1:=1 to m do
        for x2:=x1 to m do
          for y2:=y1 to m do
            begin
              for x:=x1 to x2-1 do
                begin
                  f[k,x1,y1,x2,y2]:=min( f[k,x1,y1,x2,y2],f[k-1,x1,y1,x,y2]+sum(x+1,y1,x2,y2));
                  f[k,x1,y1,x2,y2]:=min( f[k,x1,y1,x2,y2],sum(x1,y1,x,y2)+f[k-1,x+1,y1,x2,y2]);
                end;
              for y:=y1 to y2-1 do
                begin
                  f[k,x1,y1,x2,y2]:=min( f[k,x1,y1,x2,y2],f[k-1,x1,y1,x2,y]+sum(x1,y+1,x2,y2));
                  f[k,x1,y1,x2,y2]:=min( f[k,x1,y1,x2,y2],sum(x1,y1,x2,y)+f[k-1,x1,y+1,x2,y2]);
                end;
            end;
assign(output,fout);rewrite(output);
writeln(sqrt(f[n-1,1,1,8,8]/n-xx):0:3);
close(output);
end.