比赛 |
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.