http://acm.pku.edu.cn/JudgeOnline/problem?id=1191

http://acm.pku.edu.cn/JudgeOnline/images/1191_1.jpg

Код:
program PKU1191;
{$i-,s-,q-,r-}

const maxn = 15;
  maxm = 8;
  none = 1000000;

type integer = longint;

var s: array[0 .. maxm, 0 .. maxm] of integer;
    f: array[1 .. maxm, 1 .. maxm, 1 .. maxm, 1 .. maxm, 1..maxn] of double;
    n: integer;

function min(i, j: double): double;
begin
  if i < j then min := i else min := j;
end;

procedure prepare;
var i, j, k: integer;
begin
  fillchar(s, sizeof(s), 0);
  read(n);
  for i := 1 to 8 do
    for j := 1 to 8 do begin
      read(k);
      s[i, j] := s[i - 1, j] + s[i, j - 1] - s[i - 1, j - 1] + k;
    end;
end;

function calc(x0, x1, y0, y1: integer): integer;
begin
  calc := s[x1, y1] - s[x1, y0 - 1] - s[x0 - 1, y1] + s[x0 - 1, y0 - 1];
end;

procedure main;
var i, j, u, v, a, b, k: integer;
    mid: double;
begin
  mid := s[8, 8] / n;
  for i := 0 to 7 do
    for u := 1 to 8 - i do
      for j := 0 to 7 do
        for v := 1 to 8 - j do begin
          f[u, i + u, v, j + v, 1] := sqr(mid - calc(u, i + u, v, j + v));
          for k := 2 to n do begin
            f[u, i + u, v, j + v, k] := none;
            if k <= i + j then
            for a := u to i + u - 1 do begin
              f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
                 f[u, a, v, j + v, 1] + f[a + 1, i + u, v, j + v, k - 1]);
              f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
                 f[u, a, v, j + v, k - 1] + f[a + 1, i + u, v, j + v, 1]);
            end;
            for a := v to j + v - 1 do begin
              f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
                 f[u, u + i, v, a, 1] + f[u, u + i, a + 1, v + j, k - 1]);
              f[u, i + u, v, j + v, k] := min(f[u, i + u, v, j + v, k],
                 f[u, u + i, v, a, k - 1] + f[u, u + i, a + 1, v + j, 1]);
            end;
          end;
        end;
  writeln(sqrt(f[1, 8, 1, 8, n] / n):1:3);
end;

begin
  prepare;
  main;
end.