比赛 |
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;
}
}
}
}