义乌网站建设工作室,乐wordpress,邮箱购买自动发卡,seo搜索引擎优化费用该题的方法#xff0c;也有点背包的意思#xff0c;如果一些不懂的朋友#xff0c;可以从背包的角度去理解该树形DP
问题 题解主要在注释里 //该题是背包问题树形dp问题的结合版#xff0c;在树上解决背包问题 //背包问题就是选或不选当前物品 //本题求的是最大分数 //先转…
该题的方法也有点背包的意思如果一些不懂的朋友可以从背包的角度去理解该树形DP
问题 题解主要在注释里 //该题是背包问题树形dp问题的结合版在树上解决背包问题 //背包问题就是选或不选当前物品 //本题求的是最大分数 //先转成背包问题理解 //从n个物品当中选出最大分数 //再转成有限制版的 //从n个物品当中选出最大分数并且血量是健康的 //再转成树形DP去理解该问题 //树是健康就是在任意一条树的路径下(到叶子节点的任意一条路径)能确保至少有一个物品不被选 //从树上前n个物品当中选出一些物品并且保证树是健康的 //从树上前i个物品当中选出保证树是健康的前提下能选出的不超过i个物品的最大分数 //然后再去拓展这个定义 //结合树形DP的经验 //以当前u为根节点的子树在保证树是健康的前提下能选出的最大分数 //那么就有了推导过程从下往上推导也就是从最小子树往上推导到最大子树最大分数 //那么最好的做法就是利用递归的特性回溯的时候进行推导 //这题中我们直接找出最大分数其实是比较难的我们用初中的思想 //正难则反既然找最大分数(有个不选的)比较难那么我们可以用 //找个最小分数(选上的)那么就变得比较简单了 //状态定义 //首先我们找最小的以树形dp为经验推导出 //我们以u为根节点的子树总和最小的分数并且是保证健康的在一条路径上最少也得选一个 //定义为min_val[u] //那么怎么算出最大分数呢既然有min_val[u],那么就有以当前u为根节点的子树节点总和sum_val[u] //那么相减sum_val[u] - min_val[u]就等于最大分数了 //那么如何推导这两个定义的数组呢 //树形dp类型问题最好首先用dfs,边回溯边推导数组 class Solution {
public:void dfs_sum_val(int u,int fa,vectorint val,vectorvectorint g,vectorlong long sum_val){sum_val[u] val[u];for(auto e:g[u])if(fa ! e)//不要往上计算我们是从下往上推导{dfs_sum_val(e,u,val,g,sum_val);//回溯计算sum_val[u] sum_val[e];}//这个dfs我们可以算作一个小题就是计算出每个点为根节点的子树的总和}void dfs_min_val(int u,int fa,vectorint val,vectorvectorint g,vectorlong long min_val){long long min_res 0;min_val[u] (long long)val[u];for(auto e:g[u]){if(fa ! e){dfs_min_val(e,u,val,g,min_val);min_res min_val[e];}}if(min_res) min_val[u] min((long long)min_val[u],min_res);}long long maximumScoreAfterOperations(vectorvectorint edges, vectorint values) {//该题是背包问题树形dp问题的结合版在树上解决背包问题//背包问题就是选或不选当前物品//本题求的是最大分数//先转成背包问题理解//从n个物品当中选出最大分数//再转成有限制版的//从n个物品当中选出最大分数并且血量是健康的//再转成树形DP去理解该问题//树是健康就是在任意一条树的路径下(到叶子节点的任意一条路径)能确保至少有一个物品不被选//从树上前n个物品当中选出一些物品并且保证树是健康的//从树上前i个物品当中选出保证树是健康的前提下能选出的不超过i个物品的最大分数//然后再去拓展这个定义//结合树形DP的经验//以当前u为根节点的子树在保证树是健康的前提下能选出的最大分数//那么就有了推导过程从下往上推导也就是从最小子树往上推导到最大子树最大分数//那么最好的做法就是利用递归的特性回溯的时候进行推导//这题中我们直接找出最大分数其实是比较难的我们用初中的思想//正难则反既然找最大分数(有个不选的)比较难那么我们可以用//找个最小分数(选上的)那么就变得比较简单了//状态定义//首先我们找最小的以树形dp为经验推导出//我们以u为根节点的子树总和最小的分数并且是保证健康的在一条路径上最少也得选一个//定义为min_val[u]//那么怎么算出最大分数呢既然有min_val[u],那么就有以当前u为根节点的子树节点总和sum_val[u]//那么相减sum_val[u] - min_val[u]就等于最大分数了//那么如何推导这两个定义的数组呢//树形dp类型问题最好首先用dfs,边回溯边推导数组int edge_size edges.size();vectorvectorint g(values.size() 110);for(int i 0;i edge_size;i){int a edges[i][0];int b edges[i][1];g[a].push_back(b);g[b].push_back(a);}vectorlong long sum_val(21000);vectorlong long min_val(21000,0x3f3f3f3f);//预处理出来sum_val数组dfs_sum_val(0,-1,values,g,sum_val);//预处理出来min_val数组dfs_min_val(0,-1,values,g,min_val);return sum_val[0] - min_val[0];}
};
