T01191: 棋盘分割

http://cs101.openjudge.cn/practice/01191/

将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。均方差$ \sigma = \sqrt{\frac{\sum_{i=1}^{n} (x_i - \bar{x})^2}{n}} $，其中平均值$ \bar{x} = \frac{\sum_{i=1}^{n} (x_i)^2}{n} $，$ x_i$为第i块矩形棋盘的总分。请编程对给出的棋盘及n，求出 $σ$ 的最小值。

输入

第1行为一个整数n(1 < n < 15)。第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出

仅一个数，为 $σ$ （四舍五入精确到小数点后三位）。

样例输入

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

样例输出

1.633

来源: Noi 99

因为方差公式比较复杂，可先将其变形

\begin{array}{l} σ^{2} = \frac{1}{n} [(x_{1} - \bar{x})^{2} + (x_{2} - \bar{x})^{2} + . . . + (x_{n} - \bar{x})^{2}] \\ = \frac{1}{n} [(x_{1}^{2} - 2 x_{1} \bar{x} + {\bar{x}}^{2}) + (x_{2}^{2} - 2 x_{2} \bar{x} + {\bar{x}}^{2}) + . . . + (x_{n}^{2} - 2 x_{n} \bar{x} + {\bar{x}}^{2})] \\ = \frac{1}{n} (\sum x_{i}^{2} + n {\bar{x}}^{2} - 2 \bar{x} \sum_{i = 1}^{n} x_{i}) \\ = \frac{1}{n} \sum x_{i}^{2} - {\bar{x}}^{2} \end{array}

由于平均值是一定的，所以只需要让每个矩形的总分的平方和最小。

每一次分割有以下4种方法:

python

# https://blog.csdn.net/Dante__Alighieri/article/details/38823005
# https://blog.csdn.net/qq_40774175/article/details/82704582
# 时间: 93ms
from collections import defaultdict

def f(n, x1, y1, x2, y2):
    if dp[(n, x1, y1, x2, y2)] > 0:
        return dp[(n, x1, y1, x2, y2)]
    if n == 1:
        su = 0
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                su += l[i][j]
        dp[(n, x1, y1, x2, y2)] = su*su
        return su*su
    #mi = 10000000
    mi = float('inf')
    for i in range(x1, x2):
        mi = min(mi, f(n-1, x1, y1, i, y2)+f(1, i+1, y1, x2, y2))
        mi = min(mi, f(1, x1, y1, i, y2)+f(n-1, i+1, y1, x2, y2))
    for i in range(y1, y2):
        mi = min(mi, f(n-1, x1, y1, x2, i)+f(1, x1, i+1, x2, y2))
        mi = min(mi, f(1, x1, y1, x2, i)+f(n-1, x1, i+1, x2, y2))
    dp[(n, x1, y1, x2, y2)] = mi
    return mi


n = int(input())
l = []
for i in range(8):
    l.append([int(x) for x in input().split()])
s = 0
for i in l:
    for j in i:
        s += j
dp = defaultdict(int)

print("%.3f"%(f(n, 0,0,7,7)/n-s*s/n/n)**0.5)

用lru_cache维护子过程计算结果，比自己开dp空间记录，还快一点。

python

# 时间: 62ms 如果不开lru_cache超时
#from collections import defaultdict

from functools import lru_cache 

@lru_cache(maxsize = None) 

def f(n, x1, y1, x2, y2):
#    if dp[(n, x1, y1, x2, y2)] > 0:
#        return dp[(n, x1, y1, x2, y2)]
    if n == 1:
        su = 0
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                su += l[i][j]
#        dp[(n, x1, y1, x2, y2)] = su*su
        return su*su
    #mi = 10000000
    mi = float('inf')
    for i in range(x1, x2):
        mi = min(mi, f(n-1, x1, y1, i, y2)+f(1, i+1, y1, x2, y2))
        mi = min(mi, f(1, x1, y1, i, y2)+f(n-1, i+1, y1, x2, y2))
    for i in range(y1, y2):
        mi = min(mi, f(n-1, x1, y1, x2, i)+f(1, x1, i+1, x2, y2))
        mi = min(mi, f(1, x1, y1, x2, i)+f(n-1, x1, i+1, x2, y2))
#    dp[(n, x1, y1, x2, y2)] = mi
    return mi


n = int(input())
l = []
for i in range(8):
    l.append([int(x) for x in input().split()])
s = 0
for i in l:
    for j in i:
        s += j
# dp = defaultdict(int)

print("%.3f"%(f(n, 0,0,7,7)/n-s*s/n/n)**0.5)

T01191: 棋盘分割 ​

T01191: 棋盘分割