#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

#define min(x,y) x<y?x:y
#define M 8

int d[15][M+1][M+1][M+1][M+1] = {0};
int s[M+1][M+1] = {0};
int c[M+1][M+1] = {0};
int n;

void pre()
{
	int i,j;
	for(i = 0;i <= M;i++)
		s[i][0] = 0;
	for(j = 0;j <= M;j++)
		s[0][j] = 0;
	for(i = 1;i <= M;i++)
		for(j = 1;j <= M;j++)
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + c[i][j];
}
int f(int i_min,int j_min,int i_max,int j_max)
{
	int temp = s[i_max][j_max] - s[i_min-1][j_max] -s[i_max][j_min-1] +s[i_min-1][j_min-1];
	return temp*temp;
}
int main()
{
	int i,j,k,a,b,temp;
	int x1,y1,x2,y2,min_a,min_b;
	int sum = 0;
	double x,ans;
	scanf("%d",&n);
	for(i = 1;i <= M;i++)
	{
		for(j = 1;j <= M;j++)
		{
			scanf("%d",&c[i][j]);
			sum += c[i][j];
		}
	}
	x = (double)sum/n;
	
	pre();
	
	for(x1 = 1;x1 <= M;x1++)
	{
		for(y1 = 1;y1 <= M;y1++)
		{
			for(x2 = 1;x2 <= M;x2++)
			{
				for(y2 = 1;y2 <= M;y2++)
				{
					
					d[0][x1][y1][x2][y2] = f(x1,y1,x2,y2);
				}
			}
		}
	}
	
	for(k = 1;k < n;k++)
	{
		for(x1 = 1;x1 <= M;x1++)
		{
			for(y1 = 1;y1 <= M;y1++)
			{
				for(x2 = 1;x2 <= M;x2++)
				{
					for(y2 = 1;y2 <= M;y2++)
					{
						min_a = INT_MAX;
						for(a = x1;a < x2;a++)
						{
							temp = min(d[k-1][x1][y1][a][y2]+d[0][a+1][y1][x2][y2],d[k-1][a+1][y1][x2][y2]+d[0][x1][y1][a][y2]);
							if(min_a > temp)
								min_a = temp;
						}
						
						min_b = INT_MAX;
						for(b = y1;b < y2;b++)
						{
							temp = min(d[k-1][x1][y1][x2][b]+d[0][x1][b+1][x2][y2],d[k-1][x1][b+1][x2][y2]+d[0][x1][y1][x2][b]);
							if(min_b > temp)
								min_b = temp;
						}
						
						d[k][x1][y1][x2][y2] = min(min_a,min_b);
					}
				}
			}
		}
	}
	ans = (double)d[n-1][1][1][8][8]/n - x*x;
	ans = sqrt(ans);
	printf("%.3f\n",ans);
	return 0;
}

• Re:啊啊啊啊，为什么我的总是WA，哪位大侠给看下…… (2107) zgsxzdl 2010-07-21 21:36:15
  • Re:啊啊啊啊，为什么我的总是WA，哪位大侠给看下…… (17) zgsxzdl 2010-07-21 21:37:31