方差公式：D[X]=E[X^2]-(E[X])^2 E[X]是定的，求出平方和的最小值即可。 记忆化dfs一下即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define INF 0x3f3f3f3f #include<climits> typedef long long LL; using namespace std; int t[15][15][15][15][15]; int a[15][15],sum[15][15]; int n,m,k; int dfs(int a,int b,int c,int d,int k){ int &res=t[a][b][c][d][k]; if(res!=-1)return res; if(k==0){ res=(sum[c][d]+sum[a-1][b-1]-sum[c][b-1]-sum[a-1][d])*(sum[c][d]+sum[a-1][b-1]-sum[c][b-1]-sum[a-1][d]); return res; } res=INF; for(int i=a;i<=c-1;i++){ for(int j=0;j<k;j++){ res=min(res,dfs(a,b,i,d,j)+dfs(i+1,b,c,d,k-1-j)); } } for(int i=b;i<=d-1;i++){ for(int j=0;j<k;j++){ res=min(res,dfs(a,b,c,i,j)+dfs(a,i+1,c,d,k-1-j)); } } return res; } int main() { freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } memset(t,-1,sizeof(t)); //cout<<t[0][0][0][0][0]<<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } double ave=(double)sum[n][m]/k; int ss=dfs(1,1,n,m,k-1); printf("%.2lf\n",sqrt((double)ss/k-ave*ave)); return 0; }