比赛 20120919dfs 评测结果 AATTAAAATT
题目名称 棋盘分割 最终得分 60
用户昵称 苏轼 运行时间 4.323 s
代码语言 C++ 内存使用 3.13 MiB
提交时间 2012-09-19 21:28:44
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,shu=1;
int q[100][4],m[9][9]={0};
double answer=99999999;
void dfs(int x);
int main()
{
	freopen ("division.in","r",stdin);
	freopen ("division.out","w",stdout);
	cin>>n;
	for (int i=0;i<8;i++)
		for (int j=0;j<8;j++)
			cin>>m[i][j];
	q[0][0]=0;
	q[0][1]=0;
	q[0][2]=8;
	q[0][3]=8;
	dfs(0);
	printf("%.3lf",answer);
	return 0;
}
void dfs(int x)
{
	if (x==n-1)
	{
		double xxxx,bb=0,yyyy=0;
		for (int i=0;i<n;i++)
		{
			double aa=0;
			for (int j=q[i][0];j<q[i][2];j++)
			{
				for (int k=q[i][1];k<q[i][3];k++)
				{
					aa+=m[j][k];
				}
			}
			bb+=aa;
		}
		xxxx=bb/n;
		bb=0;
		for (int i=0;i<n;i++)
		{
			double aa=0;
			for (int j=q[i][0];j<q[i][2];j++)
			{
				for (int k=q[i][1];k<q[i][3];k++)
				{
					aa+=m[j][k];
				}
			}
			bb+=(aa-xxxx)*(aa-xxxx);
		}
		yyyy=sqrt(bb/n);
		if (yyyy<answer)
			answer=yyyy;
	}
	else
	{
		for (int i=0;i<shu;i++)
		{
			for (int j=q[i][0]+1;j<q[i][2];j++)
			{
				int tmp;
				q[shu][0]=j;
				q[shu][1]=q[i][1];
				q[shu][2]=q[i][2];
				q[shu][3]=q[i][3];
				tmp=q[i][2];
				q[i][2]=j;
				shu++;
				dfs(x+1);
				shu--;
				q[i][2]=tmp;
			}
			for (int j=q[i][1]+1;j<q[i][3];j++)
			{
				int tmp;
				q[shu][0]=q[i][0];
				q[shu][1]=j;
				q[shu][2]=q[i][2];
				q[shu][3]=q[i][3];
				tmp=q[i][3];
				q[i][3]=j;
				shu++;
				dfs(x+1);
				shu--;
				q[i][3]=tmp;
			}
		}
	}
}