AcWing 479. 加分二叉树(Python)
原题链接
中等
作者:
习学学
,
2021-01-29 00:11:12
,
所有人可见
,
阅读 443
n = int(input())
nodes = [0] + list(map(int, input().split()))
order = []
dp = [[0] * (n+1) for _ in range(n+1)]
root = [[0] * (n+1) for _ in range(n+1)]
def dfs(l, r):
if l > r: return
k = root[l][r]
print(k, end=" ")
dfs(l, k-1)
dfs(k+1, r)
return
for leng in range(1, n+1):
for l in range(1, n-leng+2):
r = l + leng - 1
if leng == 1:
dp[l][r] = nodes[l]
root[l][r] = l
else:
for k in range(l, r+1):
left = 1 if k == l else dp[l][k-1]
right = 1 if k == r else dp[k+1][r]
score = left * right + nodes[k]
if score > dp[l][r]:
dp[l][r] = score
root[l][r] = k
print(dp[1][n])
dfs(1, n)