POJ 1191

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn= 20;
const int INF= 0x3f3f3f3f;

int m[10][10], s[10][10];
int dp[maxn][10][10][10][10];

int SqSum(int x1, int y1, int x2, int y2)
{
	--x1;
	--y1;
	int sm= s[x1][y1]+s[x2][y2]-s[x2][y1]-s[x1][y2];
	return sm*sm;
}
void Init()
{
	memset(dp, 0x3f, sizeof(dp));
	memset(s, 0, sizeof(s));

	for (int i= 1; i<= 8; ++i){
		int ls= 0;
		for (int j= 1; j<= 8; ++j){
			ls+= m[i][j];
			s[i][j]= s[i-1][j]+ls;
		}
	}

	for (int x1= 1; x1<= 8; ++x1){
		for (int y1= 1; y1<= 8; ++y1){
			for (int x2= x1; x2<= 8; ++x2){
				for (int y2= y1; y2<= 8; ++y2){
					int sq= SqSum(x1, y1, x2, y2);
					dp[0][x1][y1][x2][y2]= sq;
				}
			}
		}
	}
}

int main()
{
	int n;
	double sg, sg2, xav, xsm= 0.0;
	scanf("%d", &n);

	for (int i= 1; i<= 8; ++i){
		for (int j= 1; j<= 8; ++j){
			scanf("%d", &(m[i][j]));
			xsm+= m[i][j];
		}
	}
	Init();

	xav= xsm/n;

	// the range of k can be optimized
	for (int k= 1; k< n; ++k){ 	
		for (int x1= 1; x1<= 8; ++x1){
			for (int y1= 1; y1<= 8; ++y1){
				for (int x2= x1; x2<= 8; ++x2){
					for (int y2= y1; y2<= 8; ++y2){
						int a, b, tmp, sq;
						tmp= INF;

						for (int x= x1; x< x2; ++x){
							sq= dp[0][x+1][y1][x2][y2];
							a= dp[k-1][x1][y1][x][y2]+sq;
							sq= dp[0][x1][y1][x][y2];
							b= dp[k-1][x+1][y1][x2][y2]+sq;
							tmp= min(tmp, min(a, b));
						}
						for (int y= y1; y< y2; ++y){
							sq= dp[0][x1][y+1][x2][y2];
							a= dp[k-1][x1][y1][x2][y]+sq;
							sq= dp[0][x1][y1][x2][y];
							b= dp[k-1][x1][y+1][x2][y2]+sq;
							tmp= min(tmp, min(a, b));
						}

						dp[k][x1][y1][x2][y2]= tmp;
					}
				}
			}
		}
	}

	sg2= double(dp[n-1][1][1][8][8])/double(n)-xav*xav;
	sg= floor(1000*sqrt(sg2)+0.5)/1000;

	printf("%.3f
", sg);
	return 0;
}