M24637: 宝藏二叉树

dp, http://cs101.openjudge.cn/practice/24637/

探险家小B发现了一颗宝藏二叉树。这棵树的树根为Root，除了Root节点之外，每个节点均只有一个父节点，因此形成了一颗二叉树。宝藏二叉树的每个节点都有宝藏，每个宝藏具有相应的价值。小B希望摘取这些宝藏，使自己的收益最大。可是，宝藏二叉树有一个奇怪的性质，在摘取宝藏的时候，如果两个节点之间有边，那么最多只能摘取其中一个节点上的宝藏，如果因为贪婪而把两个节点上的宝藏都摘取，二叉树就会立即消失，丧失所有奖励。为此，小B求助于你，希望你能给出，小B在不使宝藏二叉树消失的前提下，能够获得宝藏的最大价值。

为了简化题目，规定宝藏二叉树均为完全二叉树，树中节点如图所示自上而下，自左向右，从1-N编号。

输入

输入分为两行第一行为一个整数N，代表二叉树中节点的个数。第二行为一个N个非负整数。第i个数代表二叉树中编号为i的节点上的宝藏价值。

输出

输出为一个整数，代表小B的最大收益。

样例输入

6
3 4 5 1 3 1

样例输出

python

class Solution:
    def rob(self, values):
        from functools import lru_cache

        n = len(values)

        #@lru_cache(None)
        def dfs(i):
            if i > n:
                return 0, 0  # (rob, not_rob)

            # 左右孩子编号
            left = 2 * i
            right = 2 * i + 1

            l_rob, l_not_rob = dfs(left)
            r_rob, r_not_rob = dfs(right)

            rob_i = values[i - 1] + l_not_rob + r_not_rob
            not_rob_i = max(l_rob, l_not_rob) + max(r_rob, r_not_rob)

            return rob_i, not_rob_i

        return max(dfs(1))  # 根节点编号为1

sol = Solution()
n = int(input())
values = list(map(int, input().split()))
print(sol.rob(values))

可以把这棵完全二叉树看成一个树形上的「最大权独立集」问题——也就是在树上选若干个节点，使得没有一条边的两个端点同时被选中，且被选中节点权值之和最大。

对于任意一个节点 (i)，定义两个状态：

$f [i] [0]$ ：在以 (i) 为根的子树中，不选节点 i 时能获得的最大权值；
$f [i] [1]$ ：在以 (i) 为根的子树中，选节点 i 时能获得的最大权值。

考虑节点 i 的左右孩子编号分别为 l=2i 与 r=2i+1（如果超过 N 则不存在）：

不选 i （状态 f[i][0]）时，左右孩子可以选也可以不选，取最大：
$f [i] [0] = {\begin{cases} max (f [l] [0], f [l] [1]) & 若 l \leq N, \\ 0 & 否则 \end{cases} + {\begin{cases} max (f [r] [0], f [r] [1]) & 若 r \leq N, \\ 0 & 否则. \end{cases}$
选 i （状态 f[i][1]）时，左右孩子都不能选，只能取它们 “不选” 的状态： $f [i] [1] = v_{i} + {\begin{cases} f [l] [0] & 若 l \leq N, \\ 0 & 否则 \end{cases} + {\begin{cases} f [r] [0] & 若 r \leq N, \\ 0 & 否则. \end{cases}$

答案即为整棵树根节点 1 的这两种状态的最大值：

$max (f [1] [0], f [1] [1]) .$

由于编号是 1 到 N 的完全二叉树，我们可以直接从 i=N 递减到 1，用数组滚动完成 DP，时间复杂度 O(N)、空间复杂度 O(N)。

下面给出一个 Python 实现：

python

import sys
sys.setrecursionlimit(10**7)

def max_treasure(N, vals):
    # vals: 1-based list of length N+1
    # f[i][0], f[i][1]
    f0 = [0] * (N + 1)
    f1 = [0] * (N + 1)
    
    for i in range(N, 0, -1):
        l, r = 2*i, 2*i+1
        
        # 状态1：选i
        include = vals[i]
        if l <= N:
            include += f0[l]
        if r <= N:
            include += f0[r]
        f1[i] = include
        
        # 状态0：不选i
        not_include = 0
        if l <= N:
            not_include += max(f0[l], f1[l])
        if r <= N:
            not_include += max(f0[r], f1[r])
        f0[i] = not_include
    
    return max(f0[1], f1[1])

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().split()
    N = int(data[0])
    vals = [0] + list(map(int, data[1:]))
    print(max_treasure(N, vals))

说明：

由于是完全二叉树，孩子编号固定为 2i 和 2i+1，方便用数组索引处理。
我们从下往上（即从编号最大的叶子节点向上）计算，每个节点只需要看它的两棵子树的两个状态，不会有环，安全又高效。
最终答案是根节点不选或选的两种情况中较大的一个。

【珂有为 24工学院】思路：这个题给的标签竟然是dp,有点在意料之外，我的第一思路就是把二叉树构造出来，然后递归做(觉得就是典型的能把树构造好就能秒的树的题目)。

考试时把编号(从1开始算，不然没规律)和二叉树位置的对应关系忘了，现想的……把编号转为二进制编码，从第二位开始遍历，假如是0就往左，是1就往右，就可以找到编号对应的二叉树中的位置。

考虑以节点node为根节点的子树的答案。有两种情况，一种是不取该节点的值，那么最大值为以其左右子节点为根节点的子树的答案的和；另一种是取该节点的值，则其左右节点的值不能取。为了方便起见，额外用一个参量表示能否取根节点的值。dfs(node, flag)，flag为False，表示不能取node的值，反之则可以取。

构造好树以后dfs(root, True)即可得到答案。

python

class Node:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def InsertNode(root, v, code):
    if code == '0':
        root.left = Node(v)
        return
    elif code == '1':
        root.right = Node(v)
        return
    
    if code[0] == '0':
        InsertNode(root.left, v, code[1:])
    elif code[0] == '1':
        InsertNode(root.right, v, code[1:])

def dfs(root, flag):
    if not root:
        return 0
    
    if flag == False:
        return dfs(root.left, True) + dfs(root.right, True)
    
    return max(root.val + dfs(root.left, False) + dfs(root.right, False), dfs(root.left, True) + dfs(root.right, True))

n = int(input())
values = [0] + list(map(int,input().split()))
root = Node(values[1])
for i in range(2, n + 1):
    InsertNode(root, values[i], bin(i)[3:])

print(dfs(root, True))

【白晨旭 24工学院】很简洁，选了当前点就不能选左右儿子，相当于就是左右儿子的notchoose + 当前点；不选当前点就看左右儿子最大能有多少宝藏然后加起来。树和递归融合起来确实简洁又漂亮

python

def max_value(n, tree):
    def dfs(i):
        if i >= n:
            return 0, 0
        
        left = dfs(2 * i + 1)
        right = dfs(2 * i + 2)
        not_choose = max(left) + max(right)
        choose = left[0] + right[0] + tree[i]
        
        return not_choose, choose
    return max(dfs(0))
    
n = int(input())
values = list(map(int, input().split()))
print(max_value(n, values))

python

# 黄鑫源 24地空学院
# 用递归比较节点与孙子节点的和与子节点和的大小
n = int(input())
l = list(map(int, input().split()))


def dfs(i):
    if i >= n:
        return 0
    else:
        return max(l[i] + dfs(4 * i + 3) + dfs(4 * i + 4) + dfs(4 * i + 5) + dfs(4 * i + 6),
                   dfs(2 * i + 1) + dfs(2 * i + 2))


print(dfs(0))

M24637: 宝藏二叉树 ​

M24637: 宝藏二叉树