本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15646888.html

题目链接

题目

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

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

思路

化简式子可知原式是求：

∑i=1nxi2−(∑i=1nxi)2nn\Large\sqrt{\frac{\sum_{i=1}^n x_i^2-\frac{(\sum_{i=1}^n x_i)^2}{n}}{n}}

(∑i=1nxi)2n\frac{(\sum_{i=1}^n x_i)^2}{n} 可以直接求出来，所以主要是弄前面一部分。

设 dp(lx,ly,rx,ry,k)dp(lx, ly, rx, ry, k) 表示在 (lx,ly)(lx, ly) 到 (rx,ry)(rx, ry) 的区间里分成 kk 块每块的平方和最小值。

转移时可以考虑横切竖切的情况。

为了方便统计答案，上面的式子 ∑i=1nxi2−(∑i=1nxi)2nn\sqrt{\frac{\sum_{i=1}^n x_i^2-\frac{(\sum_{i=1}^n x_i)^2}{n}}{n}} 可以化简为：

∑i=1nxi2n−(∑i=1nxin)2\Large\sqrt{\frac{\sum_{i=1}^n x_i^2}{n}-(\frac{\sum_{i=1}^n x_i}{n})^2}

用记忆化搜索实现会更好。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Problem: 棋盘分割
// Contest: POJ - Noi 99
// URL: http://poj.org/problem?id=1191
// Memory Limit: 10 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 10
int n, m, i, j, k; 
int f[N][N][N][N][16]; 
int s[N][N], a[N][N], sigam[N][N][N][N]; 
double he; 

int sum(int lx, int ly, int rx, int ry)
{
	if(sigam[lx][ly][rx][ry]!=-1) return sigam[lx][ly][rx][ry]; 
	int Sum=s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1]; 
	return sigam[lx][ly][rx][ry]=Sum*Sum; 
}

int dfs(int lx, int ly, int rx, int ry, int k)
{
	if(f[lx][ly][rx][ry][k]!=-1) return f[lx][ly][rx][ry][k]; 
	if(k==1) return f[lx][ly][rx][ry][k]=sum(lx, ly, rx, ry); 
	int ans=999999999999; 
	for(int i=lx; i<rx; ++i)
	{
		ans=min(ans, dfs(lx, ly, i, ry, k-1)+sum(i+1, ly, rx, ry)); 
		ans=min(ans, sum(lx, ly, i, ry)+dfs(i+1, ly, rx, ry, k-1)); 
	}
	for(int i=ly; i<ry; ++i)
	{
		ans=min(ans, dfs(lx, ly, rx, i, k-1)+sum(lx, i+1, rx, ry)); 
		ans=min(ans, sum(lx, ly, rx, i)+dfs(lx, i+1, rx, ry, k-1)); 
	}
	return f[lx][ly][rx][ry][k]=ans; 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	while(scanf("%lld", &k)!=EOF)
	{
		memset(f, -1, sizeof(f)); 
		memset(sigam, -1, sizeof(sigam)); 
		memset(s, 0, sizeof(s)); 
		n=8; 
		for(i=1; i<=n; ++i)
			for(j=1; j<=n; ++j)
				a[i][j]=read(); 
		for(i=1; i<=n; ++i)
			for(j=1; j<=n; ++j)
				s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; 
		he=double(double(s[n][n])/double(k)); 
		// printf("%lld %lld %lf\n", dfs(1, 1, n, n, k), s[n][n], he); 
		printf("%.3f\n", sqrt(double(dfs(1, 1, n, n, k))/double(k)-he*he)); 
	}
	return 0; 
}