题目描述

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

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

题面描述

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

思路

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

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