题目描述
将一个矩形分割成 \(n\) 个小矩形，每个小矩形的总分为这个矩形内所有数的和。求各矩形总分均方差最小值。
具体思路
先来几个定义。
均方差：$$\sqrt{\frac{1}{n} \times \sum_{i=1}^n (a_i-avg)^2}$$
方差：$$\frac{1}{n} \times \sum_{i=1}^n (a_i-avg)^2$$
其实均方差就是方差的开方，那我们可以先求出方差，最后在开方。
考虑化简方差的式子（这里就不用大量篇幅来化简）。
化简结果：$$\frac{1}{n} \times (\sum_{i=1}^n avg^2+ \sum_{i=1}^n a_i^2- 2 avg \sum_{i=1}^n a_i)$$
其中，$$avg=\frac{1}{q} \times \sum_{i=1}^n \sum_{j=1}^m a_i$$
显然 \(avg\) 是可以预处理的。
那我们只需要维护区间和即可，显然是二维前缀和啊！
考虑区间 dp。
设 \(f_{x,y,u,v,k}\) 表示以 \((x,y)\) 为左上角，以 \((u,v)\) 为右下角的矩形分成 \(k\) 个矩形的 \(\sum_{i=1}^k a_i^2- 2\times \sum_{i=1}^k a_i\) 的最小值，其中 \(a_i\) 是每个矩形的和。
我们每次需要枚举左上角坐标 \((x,y)\)，右下角坐标 \((u,v)\)，分成 \(k\) 个矩形，分割的点 \(i\) 以及 其中一边分成的矩形个数 \(j\)。
\[f_{x,y,u,v,k}=\min \limits_{i \in [x,u),j \in [1,k)} \{ f_{x,y,u,v,k},f_{x,y,i,v,j}+f_{i+1,y,u,v,k-j} \}
\]
\[f_{x,y,u,v,k}=\min \limits_{i \in [y,v),j \in [1,k)} \{ f_{x,y,u,v,k},f_{x,y,u,i,j}+f_{x,i+1,u,v,k-j} \}
\]
即横着分割与竖着分割取最小值。
最后加上 \(avg\) 的贡献即可。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=11;
const int inf=0x3f3f3f3f;
int n,m,q;
int a[N][N],sum[N][N];
double avg,f[N][N][N][N][N];
double get(int x,int y,int u,int v){
int ans=sum[u][v]-sum[x-1][v]-sum[u][y-1]+sum[x-1][y-1];
return 1.0*ans*ans-2.0*avg*ans;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
avg=1.0*sum[n][m]/q;
for(int k=1;k<=q;k++)
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
for(int u=x;u<=n;u++)
for(int v=y;v<=m;v++){
f[x][y][u][v][k]=inf;
if(k==1)f[x][y][u][v][1]=get(x,y,u,v);
else{
for(int i=x;i<u;i++){
for(int j=1;j<k;j++){
f[x][y][u][v][k]=min(f[x][y][u][v][k],f[x][y][i][v][j]+f[i+1][y][u][v][k-j]);
}
}
for(int i=y;i<v;i++){
for(int j=1;j<k;j++){
f[x][y][u][v][k]=min(f[x][y][u][v][k],f[x][y][u][i][j]+f[x][i+1][u][v][k-j]);
}
}
}
}
double res=(avg*avg*q+f[1][1][n][m][q])*1.0/q;
printf("%.2lf",sqrt(res));
return 0;
}