Description
将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差
，其中平均值
，xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O'的最小值。
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差
请编程对给出的棋盘及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[][];
int dp[][][][][]; int sum(int i1,int j1,int i2,int j2)
{
int ret=map1[i2][j2]-map1[i1-][j2]-map1[i2][j1-]+map1[i1-][j1-]; 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=;i<=;++i)
for(int j=;j<=;++j)
scanf("%d",&map1[i][j]); for(int i=;i<=;++i)
for(int j=;j<=;++j)
map1[i][j]+=map1[i][j-]; for(int j=;j<=;++j)
for(int i=;i<=;++i)
map1[i][j]+=map1[i-][j]; for(int i1=;i1<=;++i1)
for(int j1=;j1<=;++j1)
for(int i2=i1;i2<=;++i2)
for(int j2=j1;j2<=;++j2)
dp[i1][j1][i2][j2][]=sum(i1,j1,i2,j2); for(int k=;k<N;++k)
for(int i1=;i1<=;++i1)
for(int j1=;j1<=;++j1)
for(int i2=i1;i2<=;++i2)
for(int j2=j1;j2<=;++j2)
{
minn=0x3f3f3f3f; for(int q=i1;q<i2;++q)
minn=min(minn,min(dp[i1][j1][q][j2][k-]+sum(q+,j1,i2,j2),dp[q+][j1][i2][j2][k-]+sum(i1,j1,q,j2))); for(int q=j1;q<j2;++q)
minn=min(minn,min(dp[i1][j1][i2][q][k-]+sum(i1,q+,i2,j2),dp[i1][q+][i2][j2][k-]+sum(i1,j1,i2,q))); dp[i1][j1][i2][j2][k]=minn;
} long double ans=(long double)(dp[][][][][N-]); printf("%.3f\n",sqrt(ans/N-(long double)map1[][]*map1[][]*1.0/((long double)(N)*N))); return ;
}