题目大意 给定一颗以1为根节点的树，每个节点有一个购入价格p和卖出价格q。
进入一个节点时需要花费p，离开时可以收回q，每个节点只产生一次购入和卖出。
请你选择一个遍历的顺序，要求在遍历的过程中身上的钱数不小于0，且出发时带的钱数最少。
按照遍历的顺序是指：当你选择了一颗子树之后，你需要将这个子树全部走完，才能选择其他子树。
.....................................
简化到二叉树的情况考虑，
根节点A的左右儿子分别为B和C，
如果最后停留在B，则开始带的最多钱为 min（MAX（p1,p1-q1+p2-q2+p3），max(p1，p1-q1+p3-q3+p2) ）
显然根据p>=q
答案就是min(p1-q1+p2-q2+p3，p1-q1+p3-q3+p2)；
因此可以看到，比较的是 psum-(qsum-qx)x为最后停留的一边
因此对于二叉树的情况，我们应该从qi先选大后选小
同理可以推广到多叉树的情况，还是按qi从大到小选.
刚才从多个儿子里面按顺序选的 条件是：qi先选大后选小
此时若儿子代表是一棵树的话，pi和qi的意思就应该变成了，选这棵树 所需要的最大初始钱，和返回时会剩余的钱。
这个并不是简单的把子树所有节点的p和q相加，
需要递归的过程中先算出每个子树的pt_i和pt_i才可以。
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=13240;
vectormp[N];
ll p[N],q[N];
bool cmp(int a,int b)
{
return q[a]>q[b];
//按照qi排序
}
ll get(int x,int fa)
{
for(int i=0;
i 【动态规划|hiho一下 第109周 Tower Defense Game 树DP+贪心】
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers