数据范围果断小，果断暴力。。。
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <cmath> 7 8 #define N 14 9 #define INF 1e9 10 11 using namespace std; 12 13 int a,b,n; 14 double sm[N][N],map[N][N],dp[N][N][N][N][N],sum,sumb; 15 16 inline void read() 17 { 18 scanf("%d%d%d",&a,&b,&n); 19 for(int i=1;i<=a;i++) 20 for(int j=1;j<=b;j++) 21 scanf("%lf",&map[i][j]),sum+=map[i][j]; 22 sumb=sum/n; 23 for(int i=1;i<=a;i++) 24 for(int j=1;j<=b;j++) 25 sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+map[i][j]; 26 } 27 28 inline double dfs(int x1,int y1,int x2,int y2,int cs) 29 { 30 double &res=dp[x1][y1][x2][y2][cs]; 31 if(res<INF) return res; 32 if(cs==0) 33 { 34 res=(sm[x2][y2]+sm[x1-1][y1-1]-sm[x1-1][y2]-sm[x2][y1-1])-sumb; 35 res=res*res; 36 return res; 37 } 38 for(int i=x1;i<x2;i++) 39 for(int j=0;j<=cs-1;j++) 40 res=min(res,dfs(x1,y1,i,y2,j)+dfs(i+1,y1,x2,y2,cs-j-1)); 41 for(int i=y1;i<y2;i++) 42 for(int j=0;j<=cs-1;j++) 43 res=min(res,dfs(x1,y1,x2,i,j)+dfs(x1,i+1,x2,y2,cs-j-1)); 44 return res; 45 } 46 47 inline void go() 48 { 49 for(int i=0;i<=10;i++) 50 for(int j=0;j<=10;j++) 51 for(int k=0;k<=10;k++) 52 for(int p=0;p<=10;p++) 53 for(int q=0;q<=10;q++) 54 dp[i][j][k][p][q]=INF; 55 dfs(1,1,a,b,n-1); 56 printf("%.2lf\n",sqrt(dp[1][1][a][b][n-1]/n)); 57 } 58 59 int main() 60 { 61 read(),go(); 62 return 0; 63 }