poj - 1191 - 棋盤分割（dp)

poj - 1191 - 棋盤分割（dp)

題意：將一個８*８的棋盤（每個單元正方形有個分值）沿直線（豎或橫）割掉一塊，留下一塊，對留下的這塊繼續這樣操作，總共進行n - 1次，得到n塊(1 < n < 15)矩形，每個矩形的分值就是單元正方形的分值的和，問這n個矩形的最小均方差。

——>>此題中，均方差比較，等價於方差比較，等價於平方和比較。。

狀態：dp[x1][y1][x2][y2][i]表示將(x1, y1)到(x2, y2)的矩形分割i次的最小平方和。

狀態轉移方程：dp[x1][y1][x2][y2][i] = min(dp[x1][y1][j][y2][i - 1] + nSquare[j + 1][y1][x2][y2], dp[j + 1][y1][x2][y2][i - 1] + nSquare[x1][y1][j][y2], );（水平方向切割）

dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][j][i - 1] + nSquare[x1][j + 1][x2][y2], dp[x1][j + 1][x2][y2][i - 1] + nSquare[x1][y1][x2][j]);（豎直方向切割）

兩個方向再取最小值。

#include 
#include 
#include 
#include 

using std::sqrt;
using std::min;

const int WIDTH = 8;
const int MAXN = 15 + 1;
const int INF = 0x3f3f3f3f;

int a[WIDTH + 1][WIDTH + 1];
int nSum[WIDTH + 1][WIDTH + 1][WIDTH + 1][WIDTH + 1];
int nSquare[WIDTH + 1][WIDTH + 1][WIDTH + 1][WIDTH + 1];
int dp[WIDTH + 1][WIDTH + 1][WIDTH + 1][WIDTH + 1][MAXN];

void Init()
{
    memset(nSum, 0, sizeof(nSum));
    for (int x1 = 1; x1 <= WIDTH; ++x1)
    {
        for (int y1 = 1; y1 <= WIDTH; ++y1)
        {
            for (int x2 = x1; x2 <= WIDTH; ++x2)
            {
                for (int y2 = y1; y2 <= WIDTH; ++y2)
                {
                    nSum[x1][y1][x2][y2] = nSum[x1][y1][x2 - 1][y2] + nSum[x1][y1][x2][y2 - 1] - nSum[x1][y1][x2 - 1][y2 - 1] + a[x2][y2];
                    nSquare[x1][y1][x2][y2] = nSum[x1][y1][x2][y2] * nSum[x1][y1][x2][y2];
                    dp[x1][y1][x2][y2][0] = nSquare[x1][y1][x2][y2];
                }
            }
        }
    }
}

void Dp(int n)
{
    for (int i = 1; i <= n - 1; ++i)
    {
        for (int x1 = WIDTH; x1 >= 1; --x1)
        {
            for (int y1 = 1; y1 <= WIDTH; ++y1)
            {
                for (int x2 = x1; x2 <= WIDTH; ++x2)
                {
                    for (int y2 = y1; y2 <= WIDTH; ++y2)
                    {
                        dp[x1][y1][x2][y2][i] = INF;
                        for (int j = x1; j < x2; ++j)
                        {
                            dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[x1][y1][j][y2][i - 1] + nSquare[j + 1][y1][x2][y2]);
                            dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[j + 1][y1][x2][y2][i - 1] + nSquare[x1][y1][j][y2]);
                        }
                        for (int j = y1; j < y2; ++j)
                        {
                            dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[x1][y1][x2][j][i - 1] + nSquare[x1][j + 1][x2][y2]);
                            dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[x1][j + 1][x2][y2][i - 1] + nSquare[x1][y1][x2][j]);
                        }
                    }
                }
            }
        }
    }
}

void Output(int n)
{
    double fAvg = 1.0 * nSum[1][1][8][8] / n;
    printf(%.3f
, sqrt(1.0 * dp[1][1][8][8][n - 1] / n - fAvg * fAvg));
}

void Read()
{
    for (int i = 1; i <= WIDTH; ++i)
    {
        for (int j = 1; j <= WIDTH; ++j)
        {
            scanf(%d, &a[i][j]);
        }
    }
}

int main()
{
    int n;

    while (scanf(%d, &n) == 1)
    {
        Read();
        Init();
        Dp(n);
        Output(n);
    }

    return 0;
}