记录编号	2125	评测结果	AWTWAAAWTA
题目名称	[NOI 1999]棋盘分割	最终得分	50
用户昵称	zqzas	是否通过	未通过
代码语言	C++	运行时间	2.159 s
提交时间	2008-09-12 22:31:55	内存使用	0.00 MiB

#include <stdio.h>
#include <math.h>

#define maxn 10
#define maxm 20
#define inf 9999999

const int n=8;

int a[maxm],m,data[maxn][maxn],num[maxn][maxn][maxn][maxn];
double ans;
FILE *f1,*f2;

void make(void)
{
	int i,j,x1,y1,x2,y2;
	for (x1=0;x1<n;x1++)
		for (y1=0;y1<n;y1++)
			for (x2=x1;x2<n;x2++)
				for (y2=y1;y2<n;y2++)
					for (i=x1;i<=x2;i++)
						for (j=y1;j<=y2;j++)
							num[x1][y1][x2][y2]+=data[i][j];
	
}

void check_ans(void)
{
	int i;
	double zan=0,p=0;
	for (i=0;i<m;i++)
		zan+=a[i];
	zan=zan/m;
	for (i=0;i<m;i++)
	{
		p+=(a[i]-zan)*(a[i]-zan);
	}
	p=p/m;
	p=sqrt(p);
	if (p<ans)
		ans=p;
}

void search(int x1,int y1,int x2,int y2,int now)
{
	int p,q;
	if (now>=m)
	{
		
		if (a[0]==8 && a[1]==8)
			a[0]=8;

		check_ans();
		return;
	}
	if (now==m-1)
	{
		a[now]=num[x1][y1][x2][y2];
		search(x1,y1,x2,y2,now+1);
		return;
	}
	//竖切
	if (y1!=y2)
	for (p=y1;p<y2;p++)
	{
		//矩形1
		a[now]=num[x1][p+1][x2][y2];
		search(x1,y1,x2,p,now+1);
		//矩形2
		a[now]=num[x1][y1][x2][p];
		search(x1,p+1,x2,y2,now+1);
	}
	//横切
	if (x1!=x2)
	for (q=x1;q<x2;q++)
	{
		//矩形1
		a[now]=num[q+1][y1][x2][y2];
		search(x1,y1,q,y2,now+1);
		//矩形2
		a[now]=num[x1][y1][q][y2];
		search(q+1,y1,x2,y2,now+1);
	}
	
}

void run(void)
{
	make();
	search(0,0,n-1,n-1,0);
}

void ini(void)
{
	int i,j;
	fscanf(f1,"%d",&m);
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			fscanf(f1,"%d",&data[i][j]);
	ans=inf;
}

int main(void)
{
	f1=fopen("division.in","r");
	f2=fopen("division.out","w");
	ini();
	run();
	fprintf(f2,"%.3lf",ans);
	fclose(f1);fclose(f2);
	return 0;
}