比赛 |
NOIP_3 |
评测结果 |
AWTWAAAWTA |
题目名称 |
棋盘分割 |
最终得分 |
50 |
用户昵称 |
zqzas |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2008-09-12 22:15:26 |
显示代码纯文本
#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;
}