302_规格划分矩形.cpp

划分一个由64块小正方形组成的８*８的矩形： 将原矩形分成两个矩形，在分开后的两个矩形中任选一块重复这样的划分， 这样分了(n-1)次后，连同最后剩下的矩形共有n块矩形。 原矩形上每一格有一个分值， 一块矩形的总分为其所含各格分值之和。现在需要把矩形按上述规则划分成n块矩形棋盘 ，并使各矩形总分的均方差最小。 请编程对给出的矩形及n，求出O’的最小值。

/*
划分一个由64块小正方形组成的８*８的矩形：
将原矩形分成两个矩形，在分开后的两个矩形中任选一块重复这样的划分，
这样分了（n-1）次后，连同最后剩下的矩形共有n块矩形。

原矩形上每一格有一个分值，
一块矩形的总分为其所含各格分值之和。现在需要把矩形按上述规则划分成n块矩形棋盘
，并使各矩形总分的均方差最小。
请编程对给出的矩形及n，求出O’的最小值。 

测试说明
平台会对你编写的代码进行测试：

测试输入：
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
预期输出：
1.633
*/


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

const int MAX = 1 << 30;

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