Python 代码

n = int(input())
grids = []
for _ in range(8):
    grids.append(list(map(int, input().split())))

s = [[0] * 9 for _ in range(9)]
f = [[[[[-1] * (n+1) for _ in range(9)] 
        for _ in range(9)] 
        for _ in range(9)] 
        for _ in range(9)]

for i in range(1, 9):
    for j in range(1, 9):
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grids[i-1][j-1]

X = s[8][8] / n

def get(x1, y1, x2, y2):
    global X, n
    t = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]
    return ((t - X) ** 2) /n

def dp(x1, y1, x2, y2, time):
    if f[x1][y1][x2][y2][time] != -1: return f[x1][y1][x2][y2][time]
    if time == 1:
        return get(x1, y1, x2, y2)

    tmp = float('inf')
    for k in range(x1, x2):
        t1 = get(x1, y1, k, y2)
        t2 = get(k+1, y1, x2, y2)
        tmp = min(tmp, dp(x1, y1, k, y2, time-1) + t2)
        tmp = min(tmp, dp(k+1, y1, x2, y2, time-1) + t1)

    for k in range(y1, y2):
        t1 = get(x1, y1, x2, k)
        t2 = get(x1, k+1, x2, y2)
        tmp = min(tmp, dp(x1, y1, x2, k, time-1) + t2)
        tmp = min(tmp, dp(x1, k+1, x2, y2, time-1) + t1)
    f[x1][y1][x2][y2][time] = tmp
    return tmp
print("%.3f" % dp(1, 1, 8, 8, n)**0.5)