/*
劃分一個(gè)由64塊小正方形組成的８*８的矩形：
將原矩形分成兩個(gè)矩形，在分開后的兩個(gè)矩形中任選一塊重復(fù)這樣的劃分，
這樣分了（n-1）次后，連同最后剩下的矩形共有n塊矩形。

原矩形上每一格有一個(gè)分值，
一塊矩形的總分為其所含各格分值之和。現(xiàn)在需要把矩形按上述規(guī)則劃分成n塊矩形棋盤
，并使各矩形總分的均方差最小。
請(qǐng)編程對(duì)給出的矩形及n，求出O’的最小值。?

測試說明
平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測試：

測試輸入：
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


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
預(yù)期輸出：
1.633
*/


#include?
#include?
#include?
#include?
#include?
using?namespace?std;

const?int?MAX?=?1?<
int?chessboard[9][9];
int?sums[9][9][9][9];
double?DP[20][9][9][9][9];

int?N;

int?main（）{

????double?totals?=?0.0;
????double?avg?=?0.0;

????memset（?chessboard?0?sizeof（?chessboard?）?）;
????memset（?sums???????0?sizeof（?sums?）?）;

????//fstream?fin（?“test.txt“?）;
????cin?>>?N;

????for（?int?i?=?1;?i?<=?8;?++i?）{
????????for（?int?j?=?1;?j?<=?8;?++j?）{
????????????cin?>>?chessboard[i][j];
????????????sums[i][j][i][j]?=?chessboard[i][j];
????????????totals?+=?chessboard[i][j];
????????????chessboard[i][j]?+=?chessboard[i?-?1][j]?+?chessboard[i][j?-?1]?-?chessboard[i?-?1][j?-?1];
????????}
????}

????avg?=?totals?/?（?N?*?1.0?）;

????for（?int?x1?=?1;?x1?<=?8;?++x1?）{
????????for（?int?y1?=?1;?y1?<=?8;?++y1?）{
????????????for（?int?x2?=?x1;?x2?<=?8;?++x2?）{
????????????????for（?int?y2?=?y1;?y2?<=?8;?++y2?）{
????????????????????sums[x1][y1][x2][y2]?=?chessboard[x2][y2]?-?chessboard[x1?-?1][y2]?-
???????????????????????????????????????????chessboard[x2][y1?