记录编号	42753	评测结果	AWAWAAAWWW
题目名称	[NOI 1999]棋盘分割	最终得分	50
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	0.361 s
提交时间	2012-09-28 21:49:16	内存使用	1.93 MiB

#include <cstdio>
#include <cmath>
using namespace std;

int n,map[10][10]={0},sco[10][10]={0},rec[100];
double minnum=100000000;

void dfs(int deep,int x1,int y1,int x2,int y2)
{
	int i;
	if (deep==n)
	{
		double ave,s;
		rec[deep]=sco[x2][y2]-sco[x1-1][y2]-sco[x2][y1-1]+sco[x1-1][y1-1];
		ave=0;
		s=0;
		for (i=1;i<=n;i++)
			ave+=rec[i];
		ave/=n;
		for (i=1;i<=n;i++)
		{
			s+=pow(rec[i]-ave,2.0);
			if (s>=minnum)
				return;
		}
		minnum=s;
		return;
	}
	if ((x2-x1)*(y2-y1)</*!>=*/n-deep)
		return;//short cut
	for (i=x1;i<x2;i++)
	{
		rec[deep]=sco[x2][y2]-sco[i/*+1-1*/][y2]-sco[x2][y1-1]+sco[i/*+1-1*/][y1-1];//(i+1,y1)-->(x2,y2)
		dfs(deep+1,x1,y1,i,y2);
		rec[deep]=sco[i][y2]-sco[x1-1][y2]-sco[i][y1-1]+sco[x1-1][y1-1];//(x1,y1)-->(i,y2)
		dfs(deep+1,i+1,y1,x2,y2);
	}
	for (i=y1;i<y2;i++)
	{
		rec[deep]=sco[x2][y2]-sco[x1-1][y2]-sco[x2][i/*+1-1*/]+sco[x1-1][i/*+1-1*/];//(x1,i+1)-->(x2,y2)
		dfs(deep+1,x1,y1,x2,i);
		rec[deep]=sco[x2][i]-sco[x1-1][i]-sco[x2][y1-1]+sco[x1-1][y1-1];//(x1,y1)-->(x2,i)
		dfs(deep+1,x1,i+1,x2,y2);
	}
}

int main(void)
{
	freopen("division.in","r",stdin);
	freopen("division.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=8;i++)
		for (j=1;j<=8;j++)
		{
			scanf("%d",&map[i][j]);
			sco[i][j]=sco[i-1][j]+sco[i][j-1]-sco[i-1][j-1]+map[i][j];
		}
	dfs(1,1,1,8,8);
	printf("%.3lf\n",sqrt(minnum/n));
	return(0);
}