(中等) POJ 1191 棋盘分割，DP。

Description

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

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差 $\sigma=\sqrt{\frac{\sum_{i=1}^n(x_i-\bar{x})^2}{n}}$ ，其中平均值 $\bar{x}=\frac{\sum_{i=1}^nx_i}{n}$ ，x_i为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O'的最小值。

　　题目好像很经典，DP问题，直接五维的DP，dp[i1][j1][i2][j2][k]表示从(i1,j1)到(i2,j2)切割k次的最小值。

代码如下：

// ━━━━━━神兽出没━━━━━━
//      ┏┓       ┏┓
//     ┏┛┻━━━━━━━┛┻┓
//     ┃           ┃
//     ┃     ━     ┃
//     ████━████   ┃
//     ┃           ┃
//     ┃    ┻      ┃
//     ┃           ┃
//     ┗━┓       ┏━┛
//       ┃       ┃
//       ┃       ┃
//       ┃       ┗━━━┓
//       ┃           ┣┓
//       ┃           ┏┛
//       ┗┓┓┏━━━━━┳┓┏┛
//        ┃┫┫     ┃┫┫
//        ┗┻┛     ┗┻┛
//
// ━━━━━━感觉萌萌哒━━━━━━

// Author        : WhyWhy
// Created Time  : 2015年07月18日 星期六 12时12分42秒
// File Name     : 1191.cpp

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int map1[10][10];
int dp[10][10][10][10][20];

int sum(int i1,int j1,int i2,int j2)
{
    int ret=map1[i2][j2]-map1[i1-1][j2]-map1[i2][j1-1]+map1[i1-1][j1-1];

    ret*=ret;

    return ret;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int N;
    int minn;

    scanf("%d",&N);

    for(int i=1;i<=8;++i)
        for(int j=1;j<=8;++j)
            scanf("%d",&map1[i][j]);

    for(int i=1;i<=8;++i)
        for(int j=1;j<=8;++j)
            map1[i][j]+=map1[i][j-1];

    for(int j=1;j<=8;++j)
        for(int i=1;i<=8;++i)
            map1[i][j]+=map1[i-1][j];

    for(int i1=1;i1<=8;++i1)
        for(int j1=1;j1<=8;++j1)
            for(int i2=i1;i2<=8;++i2)
                for(int j2=j1;j2<=8;++j2)
                    dp[i1][j1][i2][j2][0]=sum(i1,j1,i2,j2);

    for(int k=1;k<N;++k)
        for(int i1=1;i1<=8;++i1)
            for(int j1=1;j1<=8;++j1)
                for(int i2=i1;i2<=8;++i2)
                    for(int j2=j1;j2<=8;++j2)
                    {
                        minn=0x3f3f3f3f;

                        for(int q=i1;q<i2;++q)
                            minn=min(minn,min(dp[i1][j1][q][j2][k-1]+sum(q+1,j1,i2,j2),dp[q+1][j1][i2][j2][k-1]+sum(i1,j1,q,j2)));

                        for(int q=j1;q<j2;++q)
                            minn=min(minn,min(dp[i1][j1][i2][q][k-1]+sum(i1,q+1,i2,j2),dp[i1][q+1][i2][j2][k-1]+sum(i1,j1,i2,q)));

                        dp[i1][j1][i2][j2][k]=minn;
                    }

    long double ans=(long double)(dp[1][1][8][8][N-1]);

    printf("%.3f
",sqrt(ans/N-(long double)map1[8][8]*map1[8][8]*1.0/((long double)(N)*N)));

    return 0;
}

View Code