记录编号	2271	评测结果	AAAAAAAAAW
题目名称	[NOI 1999]棋盘分割	最终得分	90
用户昵称	francis	是否通过	未通过
代码语言	Pascal	运行时间	0.031 s
提交时间	2008-09-17 20:38:20	内存使用	0.31 MiB

program division;
const
fin='division.in';
fou='division.out';
var
a:array[1..8,1..8]of longint;
f:array[1..8,1..8,1..8,1..8,1..15]of longint;
kk,all,k,i,j,p,q,n,ii,jj:longint;
x,last:real;
f1,f2:text;

procedure init;
begin
assign(f1,fin); assign(f2,fou);
reset(f1);      rewrite(f2);
read(f1,n);
for i:=1 to 8 do
for j:=1 to 8 do
begin
 read(f1,a[i,j]);
 all:=all+a[i,j];
end;
x:=all/n;
for i:=1 to 8 do
 for j:=1 to 8 do
  for p:=i to 8 do
   for q:=j to 8 do
   begin
    for ii:=i to p do
    for jj:=j to q do
    f[i,j,p,q,1]:=f[i,j,p,q,1]+a[ii,jj];
    f[i,j,p,q,1]:=sqr(f[i,j,p,q,1]);
   end;
end;

begin
init;
for k:=2 to n do
 for i:=1 to 8 do
  for j:=1 to 8 do
   for p:=i to 8 do
    for q:=j to 8 do
    begin
    f[i,j,p,q,k]:=999999999;
     for ii:=i to p-1 do
      for kk:=1 to k-1 do
      begin
      if f[i,j,p,q,k]>f[i,j,ii,q,kk]+f[ii+1,j,p,q,k-kk] then
         f[i,j,p,q,k]:=f[i,j,ii,q,kk]+f[ii+1,j,p,q,k-kk];
      end;
     for jj:=j to q-1 do
      for kk:=1 to k-1 do
      begin
      if f[i,j,p,q,k]>f[i,j,p,jj,kk]+f[i,jj+1,p,q,k-kk] then
         f[i,j,p,q,k]:=f[i,j,p,jj,kk]+f[i,jj+1,p,q,k-kk];
      end;
    end;
last:=f[1,1,8,8,n]+n*sqr(x)-2*x*all;
last:=last/n;
last:=sqrt(last);
last:=last*1000;
k:=round(last);
last:=k/1000;
write(f2,last:0:3);
close(f1); close(f2);
end.