发现最近好少写博客啊（其实是各种摆去了）
更一点吧
这道题要求最小化均方差，其实凭直觉来说就是要使每个块分的比较均匀一点，但是单单想到想到这些还是不够的，
首先f[i][j][k][l][t]表示以(i,j)为左上角，(k,l)为右下角，一共分割的t次的矩形的最小xx，
其中xx是某个与最小均方差挂钩的东西，
通常这种要求推式子的题目都要从小的情况推广到所有情况。
这道题也是一样的，
对于一个被分为x1和x2的矩形而言（分割了一次），用X表示平均数，
那么X=权值和/块数，
那么方差为：[(X - x1)^2 + (X - x2)^2] / 块数
对于固定的分割次数而言，块数是固定的，所以不管它，
那么我们就是要化简[(X - x1)^2 + (X - x2)^2]
原式=X^2 + x1^2 - 2 * X * x2 + X^2 + x2^2 - 2 * X * x2
=2(X ^ 2) + (x1^2 + x2^2) - 2 * X * (x1 + x2)
观察到x1+ x2就是权值和，是固定的，
而因为块数固定,X也是固定的，因此我们唯一可以改变的就是中间的平方部分，
所以我们的问题就转化为了一个矩形分割n-1次，求最小的平方和，
于是就可以直接dp了
f[i][j][k][l][t]表示以(i,j)为左上角，(k,l)为右下角，一共分割的t次的矩形的最小平方和，
同时为了满足dp性质（要求大状态先求小状态），左上角要倒着枚举，然后右下角正着枚举，
然后枚举分割线，枚举每块小矩形分割了多少次，最后计算一下即可
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 11
int ll,rr,n;
int f[AC][AC][AC][AC][AC];
int s[AC][AC],sum[AC][AC];
double ans,x;
/*以分两块（分别含有两小块）的合成为例
f[x]=((X - x1) ^ 2 + (X - x2) ^ 2)/2
对分子化简得：2 * X ^ 2 + x1 ^ 2 + x2 ^ 2 - 2 * X * (x1 + x2),
可以发现x1 + x2就是这一块的权值和，X为平均值，也就是权值和/块数，
也就是说对于任意一种分法，影响最终答案的只有x1 ^ 2 + x2 ^ 2这种，
所以只要最小化这个就可以了*/ inline void upmin(int &a,int b)
{
if(b < a) a=b;
} void pre()
{
memset(f,,sizeof(f));
scanf("%d%d%d",&ll,&rr,&n);
for(R i=;i<=ll;i++)
for(R j=;j<=rr;j++)
scanf("%d",&s[i][j]);
for(R i=;i<=ll;i++)
for(R j=;j<=rr;j++)
sum[i][j]=s[i][j] + sum[i-][j] + sum[i][j-] - sum[i-][j-];
for(R i=;i<=ll;i++)
for(R j=;j<=rr;j++)
for(R k=i;k<=ll;k++)
for(R l=j;l<=rr;l++)
{
int a=sum[k][l] - sum[i-][l] - sum[k][j-] + sum[i-][j-];
f[i][j][k][l][]=a * a;
}
/*for(R i=1;i<=ll;i++)
{
for(R j=1;j<=rr;j++)
{
printf("%d ",sum[i][j]);
}
printf("\n");
}*/
} void work()
{
for(R t=;t<n;t++)
for(R i=ll; i ;i--)//为了维护dp的条件，左上角应该要倒着枚举吧
for(R j=rr; j ;j--)//枚举左上角
{
for(R k=i;k<=ll;k++)
for(R l=j;l<=rr;l++)//枚举右上角
{
if(i == k && j == l) continue;
for(R p=j;p<l;p++)//枚举竖着的分界线
for(R tt=;tt<t;tt++)//原来的两块切割次数之和只能为t-1，因为现在切的就是第t次
upmin(f[i][j][k][l][t],f[i][j][k][p][tt] + f[i][p+][k][l][t - tt - ]);
for(R p=i;p<k;p++)//枚举横着的分界线
for(R tt=;tt<t;tt++)//枚举两块分别切了多少次,注意从0开始！！！
upmin(f[i][j][k][l][t],f[i][j][p][l][tt] + f[p+][j][k][l][t - tt - ]);
//printf("%d %d %d %d %d = %d\n",i,j,k,l,t,f[i][j][k][l][t]);
}
}
x=(double)sum[ll][rr] / (double)n;//获取平均值
ans=(double)(n * x * x) + (double)f[][][ll][rr][n-] - (double) * x * sum[ll][rr];
ans/=(double)n;
ans=sqrt(ans);
printf("%.2lf\n",ans);
} int main()
{
// freopen("in.in","r",stdin);
pre();
work();
// fclose(stdin);
return ;
}