zhanGTao_
zhanGTao_
全部文章
题解
未归档(1)
归档
标签
去牛客网
登录
/
注册
zhanGTao_的博客
全部文章
/ 题解
(共2篇)
题解 | #旅游#
非树形DP做法 (贪心) 由于整个图是一个树形结构,且起点固定为 sss 那么与 sss 相邻的点就必然不去,于 sss 距离为 222 的点可选择是否去。 贪心的思路是叶子节点必选,往上可选节点必选一定可以构造出最优解(最优解不唯一但能保证是其中一个最优解)。 证明如下: ①树形结构中的叶子节点是...
C++
贪心
深度优先搜索
2021-10-19
0
385
题解 | #小红的树#
非树形DP做法 知识点:DFS序维护子树信息,前缀和 由于DFS过程是遍历当前节点的全部子节点后返回当前节点,所以利用这个性质可以有效维护子树信息。 DFS过程中使用一个时间戳 dfndfndfn 并记录进入某个节点的时间 ininin 和出这个节点的时间 outoutout 。我们记录一个DFS序...
C++
深度优先搜索
前缀和
2021-10-19
0
549