更好的阅读体验

题目描述

将一个矩形分割成 $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;
}

题解：

平均值一开始可以直接算，然后直接记忆化搜索就好了。f[a][b][c][d][k]表示左上角为(a,b)，右下角为(c,d)的矩形被划分了k次后的最小答案。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N (12)
using namespace std;

double ave,f[N][N][N][N][N];
int n,m,p,x,sum[N][N];

double Dfs(int a,int b,int c,int d,int k)
{
    double &x=f[a][b][c][d][k];
    if (x>=0) return x;
    if (k==0)
    {
        x=sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1];
        return x=(x-ave)*(x-ave);
    }
    x=1e18;
    for (int i=a+1; i<=c; ++i)
        for (int j=0; j<k; ++j)
            x=min(x,Dfs(a,b,i-1,d,j)+Dfs(i,b,c,d,k-j-1));
    for (int i=b+1; i<=d; ++i)
        for (int j=0; j<k; ++j)
            x=min(x,Dfs(a,b,c,i-1,j)+Dfs(a,i,c,d,k-j-1));
    return x;
}

int main()
{
    memset(f,-0x7f,sizeof(f));
    cin>>n>>m>>p;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
        {
            scanf("%d",&x);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
        }
    ave=sum[n][m]*1.0/p;
    Dfs(1,1,n,m,p-1);
    printf("%.2lf",sqrt(f[1][1][n][m][p-1]/p));
 }