http://acm.pku.edu.cn/JudgeOnline/problem?id=1191
Код:
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.