题面描述

在一个满二叉树结构的网络中，节点上标有年度维护成本的非负整数。给定节点的数量和其对应的成本值，要求通过撤销一些节点来最大化节省的维护成本，但不能同时撤销原本直接相邻的两个节点。需要根据输入的节点信息，输出能够节省的最大维护成本。

思路

这道题是洛谷P1352-没有上司的舞会一题的改版.具体做法是树形$DP$.

动态规划题目重点有两个:状态定义,状态转移.

题目描述

这天小明在优化他以前做过的一个网络部署的项目，由于软件技术的提升，可以撤销部署网络中的某些节点，以简化网络并降低维护成本。但是，在撤销节点时，不能同时撤销原本直接相邻的两个节点。给定一个满二叉树结构的网络，每个节点上都标有一个数值，表示该节点的年度维护成本。现在要求撤销一些节点，使得可以节省最大的维护成本。

输入的网络以广度优先遍历的方式给出，每个节点都有一个非负整数值表示其年度维护成本。若某个节点不存在，则以$0$表示。每个数值的范围为 $0$ 到 $1000$。

输入描述

输入第一行为一个正整数$N$，表示后面有$N$个数值。其中$1 \leq$N$\leq 10000$

输入第二行为$N$个非负整数，表示网络节点每年的维护成本，按照满二叉树的广度优先遍历顺序给出。$0$ 表示不存在该关联节点，$0$ 只会存在于叶子节点上。

输出描述

输出能够节省的最大维护成本。

示例1

输入

7
5 3 5 0 6 0 1

输出

12

解释：

能够节省的最大维护成本为$5$ +$6$ + $1$ = $12$。

示例2

输入

7
2 7 8 2 4 9 2

输出

19

解释：

能够节省的最大维护成本为 $2$ + $2$ + $4$ + $9$ + $2$ = $19$.