把一个大矩阵分割成n个矩阵,使它们的方差最小。
g[i,j,k,l,path]表示(i,j) 到 (k,l) 的矩阵分割成path个的最小方差,然后暴力搜索+记忆化
O(n^5) (n<=10) ,无压力水过。
Program b;
const
maxn=10;
var
n,m,i,j,k,l,deltax,r:longint;
delta:double;
f:array[1..maxn,1..maxn] of longint;
sum:array[1..maxn,1..maxn,1..maxn,1..maxn] of double;
g:array[1..maxn,1..maxn,1..maxn,1..maxn,1..maxn] of double;
function min(a,b:double):double;
begin
if a<b then exit(a) else exit(b);
end;
function dfs(x,y,k,l,path:longint):double;
var
i,j:longint;
ans:double;
begin
if g[x,y,k,l,path]<>0 then exit(g[x,y,k,l,path]);
if path=1 then
begin
g[x,y,k,l,1]:=sum[x,y,k,l]-delta;
g[x,y,k,l,1]:=g[x,y,k,l,1]*g[x,y,k,l,1];
exit(g[x,y,k,l,1]);
end;
ans:=maxlongint;
for i:=x to k-1 do
for j:=1 to path-1 do
ans:=min(ans,dfs(x,y,i,l,j)+dfs(i+1,y,k,l,path-j));
for j:=y to l-1 do
for i:=1 to path-1 do
ans:=min(ans,dfs(x,y,k,j,i)+dfs(x,j+1,k,l,path-i));
g[x,y,k,l,path]:=ans;
exit(ans);
end;
begin
read(n,m,r);
deltax:=0;
for i:=1 to n do
for j:=1 to m do
begin
read(f[i,j]);
sum[i,j,i,j]:=f[i,j];
inc(deltax,f[i,j]);
end;
delta:=deltax/r;
for i:=1 to n do
for j:=1 to m do
begin
for k:=i+1 to n do
begin
sum[i,j,k,j]:=sum[i,j,k-1,j]+f[k,j];
end;
for l:=j+1 to m do
begin
sum[i,j,i,l]:=sum[i,j,i,l-1]+f[i,l];
end;
for k:=i+1 to n do
for l:=j+1 to n do
begin
sum[i,j,k,l]:=sum[i,j,k-1,l]+sum[i,j,k,l-1]-sum[i,j,k-1,l-1]+f[k,l];
end;
end;
fillchar(g,sizeof(g),0);
writeln(sqrt(dfs(1,1,n,m,r)/r):2:2);
end.
·