文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共2篇）

题解 | #旅游#

从题目中给出的n个结点n-1条边可知输入的是一棵树，可知是树形DP。简历二维dp数组，dp[i][0]表示在第i个结点住宿时能旅游的最长天数，dp[i][1]表示不在第i个结点住宿时能旅游的最长天数。第二维只有0和1两个取值，表示是否在第i个结点住下。在计算dp数组时，采用深度优先遍历。为此，使用邻...

C++ 树形dp 动态规划

2021-11-05

0 488

题解 | #小红的树#

开始时考虑的是暴力解法。构建树的过程就不说了。这里有一点需要注意，题目中的树并非二叉树，只是一个无环连通图，所以树节点中只能设定保存父节点的指针。在每次统计节点x的子节点中红色节点的个数时，使用一个辅助队列，开始时将x结点入队。进入循环后，查看队头结点是否为红色，然后遍历整棵树的所有结点，当遇到父节...

C++ 动态规划树形dp

2021-11-04

3 2172