欢迎光临散文网 会员登陆 & 注册

CF竞赛题目讲解_CF1084D(树形DP)

2022-09-13 10:08 作者:Clayton_Zhou  | 我要投稿

https://codeforces.com/problemset/problem/1084/d

题意:

每个节点都有自己的价值,从一个节点走到另一个节点会消耗固定值cost,但也会得到这个节点的价值,问怎样走才能得到最大的价值(从一个节点走到另一个节点)。


思路:

利用树形结构进行dp,初始化每个点的价值为自身价值,

对于每个节点都判断更新它的值或者不更新,从底向上进行dfs递归,

更新出最优ans,从一个节点到另一个节点的收益为(目标节点价值-路上消耗的价值)


dp[i] 保存从i 节点开始走向子节点得到的最大价值

状态转移:

dp[x]=max(dp[x],a[x]+dp[j]-k); // dp[i] 保存从i 节点开始走向子节点一条路径得到的最大价值

 


CF竞赛题目讲解_CF1084D(树形DP)的评论 (共 条)

分享到微博请遵守国家法律