#include <iostream>
#include <cmath>
using namespace std;
int data[10][10], n;
int dp[16][10][10][10][10];
int sum[10][10];
#define min(a,b) ( (a)<(b)?(a):(b) )
#define inf 1<<30
void get_sum(){
memset( sum, 0, sizeof(sum) );
for( int x= 1; x<= 8; ++x )
for( int y= 1; y<= 8; ++y )
sum[x][y]= sum[x-1][y]+ sum[x][y-1]- sum[x-1][y-1]+ data[x][y];
}
int calc( int x1, int y1, int x2, int y2 ){
int t= sum[x2][y2]- sum[x2][y1-1]- sum[x1-1][y2]+ sum[x1-1][y1-1];
return t* t;
}
int run_dp( int level, int x1, int y1, int x2, int y2 ){
int tmp= inf;
if( dp[level][x1][y1][x2][y2]>= 0 ) return dp[level][x1][y1][x2][y2];
if( level== 1 ) {
tmp= calc( x1, y1, x2, y2 );
dp[1][x1][y1][x2][y2]= tmp;
return dp[1][x1][y1][x2][y2]; }
for( int a= x1; a< x2; ++a ){
tmp= min( tmp, run_dp( level- 1, x1, y1, a, y2 )+ calc( a+ 1, y1, x2, y2 ) );
tmp= min( tmp, run_dp( level- 1, a+ 1, y1, x2, y2 )+ calc( x1, y1, a, y2 ) );
}
for( int a= y1; a< y2; ++a ){
tmp= min( tmp, run_dp( level- 1, x1, y1, x2, a )+ calc( x1, a+ 1, x2, y2 ) );
tmp= min( tmp, run_dp( level- 1, x1, a+ 1, x2, y2 )+ calc( x1, y1, x2, a ) );
}
dp[level][x1][y1][x2][y2]= tmp;
return tmp;
}
int main()
{
scanf("%d",&n );
double sum= 0;
for( int i= 1; i<= 8; ++i )
for( int j= 1; j<= 8; ++j ){
scanf("%d", &data[i][j] );
sum+= data[i][j]; }
get_sum(); sum/= n ;
memset( dp, -1, sizeof(dp) );
double avg= (double)run_dp( n, 1, 1, 8, 8 );
double ans= sqrt( avg/ n- sum* sum );
printf("%.3lf\n", ans );
return 0;
}
posted on 2009-05-22 20:07
Darren 閱讀(332)
評論(1) 編輯 收藏 引用