本题将棋盘划分为 $n$ 个子棋盘,需要求这 $n$ 个子棋盘的均方差。设第 $i$ 个子棋盘的分值为 $s_i$,所有子棋盘的分值之和等于所有方格分值之和,有如下公式:
$$
S = \sum_{i=1}^{n}s_i = \sum_{i=1}^{8}\sum_{j=1}^{8} a_{ij}
$$
$n$ 个子棋盘分值的均值为:
$$
\bar s = \frac{1}{n} \cdot \sum_{i=1}^{n}s_i = \frac{1}{n} \cdot S
$$
$n$ 个子棋盘分值的均方差为 $\delta ^2$,有如下公式:
$$ n \cdot \delta ^2 = \sum_{i=1}^{n}(s_i - \bar s)^2 = \sum_{i=1}^{n}(s_i - \frac{S}{n})^2 $$
而 $ \displaystyle \frac{S}{n}$ 和如何划分棋盘无关,可以预处理计算。在每划分出来一个子棋盘的时候,就计算当前的 $\displaystyle (s_i - \frac{S}{n})^2$,最后再把所有的项相加就可以了。
使用 DFS 爆搜,时间复杂度为 $(8!)^2$,肯定超时了,可以使用记忆化搜索策略。