[BOJ 13325, Python] 二进制树

问题链接

boj 13325

分类

动态程序设计, 树, 树中的动态程序设计

描述

如果你和我一样，是那种即使不能马上解决问题，也会长期坚持的人！

于是，那些我尝试了却无法解决的问题，那些我努力了却无法解决的问题，就这样和竞赛题一起堆积起来......

为了摆脱它们，我有时会通读试题，细细咀嚼，真庆幸今天终于在这篇文章中找到了解决办法！

距离我第一次尝试已经过去 8 个月了，上次尝试后我又修补了几次，但似乎都没有效果。

def pre_order_detail(graph_dict: dict, target_node: int = 1) -> list:

    result = [target_node]

    if len(graph_dict[target_node]) >= 1:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][0]):
            result.append(each_element)
        result.append(target_node)

    if len(graph_dict[target_node]) >= 2:
        for each_element in pre_order_detail(graph_dict, graph_dict[target_node][1]):
            result.append(each_element)
        result.append(target_node)

    return result

我最初的想法是使用类似上述递归函数形式的潜在遍历的变体，拍摄访问节点的图片，将其放入类似堆栈的数据结构中，然后遍历每个主干。

不过，经过思考，我意识到如果将比较对象限定为来自同一父节点的树干，那么只需将两个值中较大的一个加到父树干上，这样会更简洁！

后来，我解决了这类问题，并将其归类为树形 DP。我认为它与 DP 非常相似。

解题代码

# 이진 트리

import sys

input = sys.stdin.readline

tree_height = int(input())
node_number = pow(2, tree_height + 1)

edges = [0] + list(map(int, input().split()))
edge_sum = sum(edges)

now_start = node_number // 2 - 1
now_end = node_number - 1

while now_end:

    for i in range((now_end - now_start) // 2):

        child_edge = now_start + (2 * i)
        next_node = child_edge // 2

        edges[next_node] += max(edges[child_edge], edges[child_edge + 1])
        edge_sum += abs(edges[child_edge] - edges[child_edge + 1])

    now_end = now_start
    now_start = now_start // 2

print(edge_sum)

代码长度和时间复杂度比我们最初想象的要简单。现在我们把代码编排成这样，肯定是自下而上的。