题解 | #[NOIP2003]加分二叉树#

两次递归，区间dp，补一个python版本

N = 32
w = [0] * (N + 1)
f = [[0] * (N + 1) for _ in range(N + 1)]
root = [[0] * (N + 1) for _ in range(N + 1)]

def solve(l, r):
    if f[l][r] != 0:
        return f[l][r]
    if l == r:
        return w[l]
    if l > r:
        return 1
    for i in range(l, r + 1):
        res = solve(l, i - 1) * solve(i + 1, r) + w[i]
        if res > f[l][r]:
            f[l][r] = res
            root[l][r] = i
    return f[l][r]

def print_tree(l, r):
    if l == r:
        print(l, end=" ")
        return
    if l > r:
        return
    print(root[l][r], end=" ")
    print_tree(l, root[l][r] - 1)
    print_tree(root[l][r] + 1, r)

n = int(input())
w[1:n+1] = map(int, input().split())

print(solve(1, n))
print_tree(1, n)