记录编号	248943	评测结果	AWAWAAAWWW
题目名称	[NOI 1999]棋盘分割	最终得分	50
用户昵称	Sky_miner	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-11 16:53:00	内存使用	0.00 MiB

#include<cstdio>
#include<cmath>
using namespace std;
namespace cat{
	const int maxn=9;
	const int INF=0x3fffffff;
	const int m = 8 ;
	int num[maxn][maxn];
	int f[maxn][maxn][maxn][maxn][14];//f[起始x端点][起始y端点][末x端点][末y端点][分割次数]
	inline int sum(const int &x1,const int &y1,
	const int &x2,const int &y2){
		return num[x2][y2]-num[x2][y1-1]-num[x1-1][y2]+num[x1-1][y1-1];
	}
	inline int cat_min(const int &a,const int &b){
		return a<b?a:b;
	}
	int doo(){
		int n;scanf("%d",&n);
		int t;
		//计算矩阵中的和 
		for(int i=1;i<=m;i++)
			for(int j=1;j<=m;j++){
				scanf("%d",&t);
				num[i][j]=t+num[i-1][j]+num[i][j-1]-num[i-1][j-1];
			}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=m;j++){	//枚举长、宽 
				for(int x1=1;x1+i-1<=m;x1++){
					for(int y1=1;y1+j-1<=m;y1++){//枚举起始端点 
						int x2=x1+i-1,y2=y1+j-1; //计算出末端点 					
						//*sum(x1,y1,x2,y2);
						f[x1][y1][x2][y2][0] = sum(x1,y1,x2,y2);
						f[x1][y1][x2][y2][0]*=f[x1][y1][x2][y2][0]; 
						//f[]中存入∑(i=1 to n)xi^2 ; 
						for(int k=1;k<n;k++){
							f[x1][y1][x2][y2][k] = INF ;
							for(int l=x1;l<x2;l++){
								for(int s=0;s<k;s++) {//枚举纵向划分 
									f[x1][y1][x2][y2][k] = 
									cat_min(f[x1][y1][x2][y2][k],
									f[x1][y1][l][y2][s]+f[l+1][y1][x2][y2][k-s-1]);
								}
							}
							for(int l=y1;l<y2;l++) {//枚举横向划分 
								for(int s=0;s<k;s++)
								f[x1][y1][x2][y2][k] =
								cat_min(f[x1][y1][x2][y2][k],
								f[x1][y1][x2][l][s]+f[x1][l+1][x2][y2][k-s-1]);
							}
						}
					}
				}		
			}	
		}
			
		//ans 	= sqrt( (f[])/n - x_^2 )
		//		= sqrt( (f[])/n - (sum[m][m]/n)*(sum[m][m]/n) )
		// 注意类型,强转为double 
		double ans = (((double)f[1][1][m][m][n-1]) - ((double)num[m][m]/(double)n)*((double)num[m][m]))/(double)n;
		printf("%.3lf\n",sqrt(ans));
		return 0;
	}
}
FILE *___=freopen("division.in","r",stdin);
FILE *_=freopen("division.out","w",stdout);
int ans = cat::doo();
int main(){;}