Description
将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了（n-1)次后，原矩阵被分割成了n个矩阵。（每次分割都只能沿着数字间的缝隙进行）原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵，并使各矩阵总分的均方差最小。请编程对给出的矩阵及n，求出均方差的最小值。
Input
第一行为3个整数，表示a,b,n(1
Output
仅一个数，为均方差的最小值（四舍五入精确到小数点后2位）
Sample Input
5 4 4
2 3 4 6
5 7 5 1
10 4 0 5
2 0 2 3
4 1 1 1
Sample Output
0.50
记忆化搜索，f[i,j,k,l,n]表示矩形（i,j,k,l）分成n块最小方差（最后再除以n，一开始没除，我真的是个傻×，方差都不会算）
const
inf=;
var
f:array[..,..,..,..,..]of double;
aa:array[..,..]of double;
a,b,n:longint;
sum:double; function min(x,y:double):double;
begin
if x<y then exit(x);
exit(y);
end; function fn(x1,x2,y1,y2,k:longint):double;
var
i,j:longint;
begin
if f[x1,x2,y1,y2,k]<inf then exit(f[x1,x2,y1,y2,k]);
if (x2-x1+)*(y2-y1+)<k then exit(inf);
for i:=x1 to x2- do
for j:= to k- do
f[x1,x2,y1,y2,k]:=min(f[x1,x2,y1,y2,k],fn(x1,i,y1,y2,j)+fn(i+,x2,y1,y2,k-j));
for i:=y1 to y2- do
for j:= to k- do
f[x1,x2,y1,y2,k]:=min(f[x1,x2,y1,y2,k],fn(x1,x2,y1,i,j)+fn(x1,x2,i+,y2,k-j));
exit(f[x1,x2,y1,y2,k]);
end; procedure main;
var
i,j,k,l,r:longint;
begin
read(a,b,n);
for i:= to a do
for j:= to b do
begin
read(aa[i,j]);
sum:=sum+aa[i,j];
aa[i,j]:=aa[i,j]+aa[i-,j]+aa[i,j-]-aa[i-,j-];
end;
sum:=sum/n;
for i:= to a do
for j:=i to a do
for k:= to b do
for l:=k to b do
for r:= to n do
f[i,j,k,l,r]:=inf;
for i:= to a do
for j:=i to a do
for k:= to b do
for l:=k to b do
f[i,j,k,l,]:=sqr(aa[j,l]+aa[i-,k-]-aa[j,k-]-aa[i-,l]-sum);
write(sqrt(fn(,a,,b,n)/n)::);
end; begin
main;
end.