记录编号	249103	评测结果	AATAAAAATT
题目名称	[NOI 1999]棋盘分割	最终得分	70
用户昵称	liu_runda	是否通过	未通过
代码语言	C++	运行时间	3.446 s
提交时间	2016-04-12 06:16:30	内存使用	1.89 MiB

#include<cstdio>
#include<cassert>
#include<cmath>
#include<cstring>
const int INF=1684300900;
int a[9][9],sum[9][9];
int f[9][9][9][9][64];
int s(int x1,int y1,int x2,int y2){
	return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
double sq(double x){
	return x*x;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
int ans(int x1,int y1,int x2,int y2,int k){
//	if(f[x1][y1][x2][y2][k]!=INF)return f[x1][y1][x2][y2][k];
	if(k==1)return sq(s(x1,y1,x2,y2));
	else{
		for(int j=1;j<k;++j){
			for(int i=x1;i<x2;++i){
				f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],(long long)ans(x1,y1,i,y2,j)+(long long)ans(i+1,y1,x2,y2,k-j));
			}
			for(int i=x1;i<x2;++i){
				f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],(long long)ans(i+1,y1,x2,y2,j)+(long long)ans(x1,y1,i,y2,k-j));
			}
			for(int i=y1;i<y2;++i){
				f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],(long long)ans(x1,y1,x2,i,j)+(long long)ans(x1,i+1,x2,y2,k-j));
			}//不转成long long，INF+INF会爆int
			for(int i=y1;i<y2;++i){
				f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],(long long)ans(x1,i+1,x2,y2,j)+(long long)ans(x1,y1,x2,i,k-j));
			}
		}
	//	assert(f[x1][y1][x2][y2][k]!=-926365496);
		return f[x1][y1][x2][y2][k];
	}
}
int main(){
	freopen("division.in","r",stdin);
	freopen("division.out","w",stdout);
	int k;scanf("%d",&k);
	for(int i=1;i<=8;++i)
		for(int j=1;j<=8;++j){
			scanf("%d",&a[i][j]);
			sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
		}
//	init();
	memset(f,100,sizeof(f));
	printf("%.3lf\n",sqrt(ans(1,1,8,8,k)/double(k)-sq(s(1,1,8,8)/double(k))));
	fclose(stdin);fclose(stdout);
	return 0;

}
/*

4
5 3 1 1 1 1 3 5
3 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 3
5 3 1 1 1 1 3 5


*/