[NOI1999]棋盘分割

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

【问题描述】
  将一个8×8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将分割过的部分任选一块继续如此分割,这样割了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