ac1199.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1199;
const
  size=8;
var
  a:array[1..size,1..size]of byte;
  s:array[0..size,0..size]of word;
  best:array[boolean,1..size,1..size,1..size,1..size]of real;
  n,i,j,k,u,v,w:byte;
  m,t:real;
  b1,b2:boolean;
function sum(i,j,u,v:byte):word;
  begin
    sum:=s[u,v]+s[i-1,j-1]-s[i-1,v]-s[u,j-1];
  end;
begin
  repeat
    read(n);
    for i:=1 to size do
      for j:=1 to size do begin
        read(a[i,j]);
        s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
      end;

    fillchar(best[true],sizeof(best[true]),0);
    for k:=2 to n do begin
      b1:=odd(k);b2:=not b1;
      for i:=1 to size do
        for j:=1 to size do
          for u:=i to size do
            for v:=j to size do begin
              m:=3e38;
              for w:=i to u-1 do begin
                t:=best[b2,w+1,j,u,v]+sqr(sum(i,j,w,v))+sqr(sum(w+1,j,u,v))/(k-1);
                if t<m then m:=t;
                t:=best[b2,i,j,w,v]+sqr(sum(w+1,j,u,v))+sqr(sum(i,j,w,v))/(k-1);
                if t<m then m:=t;
              end;
              for w:=j to v-1 do begin
                t:=best[b2,i,w+1,u,v]+sqr(sum(i,j,u,w))+sqr(sum(i,w+1,u,v))/(k-1);
                if t<m then m:=t;
                t:=best[b2,i,j,u,w]+sqr(sum(i,w+1,u,v))+sqr(sum(i,j,u,w))/(k-1);
                if t<m then m:=t;
              end;
              best[b1,i,j,u,v]:=m-sqr(sum(i,j,u,v))/k;
            end;
    end;
    writeln(sqrt(best[b1,1,1,size,size]/n):0:3);
  until seekeof;
end.