第二试－棋盘分割

成绩 0 开启时间 2013年02月21日 星期四 23:01
折扣 0.8 折扣时间 2013年02月28日 星期四 23:01
允许迟交 是 关闭时间 2013年02月28日 星期四 23:01
输入文件 division.in 输出文件 division.out

【问题描述】
  将一个８×８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将分割过的部分任选一块继续如此分割，这样割了n-1次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

    原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差 ，其中平均值 x i 为第 i 块矩形棋盘的分。
请编程对给出的棋盘及 n ，求出 的最小值。
 
【输入格式】
第 1 行为一个整数 n(1

第 2 行至第 9 行每行为 8 个小于 100 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

【输出格式】
   
仅一个数，为 （四舍五入精确到小数点后三位）。
【输入样例】
输入文件名：division.in
3
1 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
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
输出文件名：division.out
1.633