A fresh start.

标签 树形dp 下的文章

December 8, 2018

UVA1292 Strategic game

跟舞会那道题差不多,如果父节点没有取那么所有子节点都必须取;如果父节点取了,子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了,这就意味着只能有一个点作为根节点,所以应该连单向边,并且事先找到那个点作为根节点。st...
December 7, 2018

洛谷1122 最大子树和

题目链接:https://www.luogu.org/problemnew/show/P1122大水题,题意就跟题目名一样,决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ,显然要当前子树和要大于0我们才会取,然后dfs即可。方程式:$$f[x]+=max(f[y],0)$$struct Edge{ int next,to; } edge[32005]; int s[1600...
December 6, 2018

洛谷2014 选课

题目链接:https://www.luogu.org/problemnew/show/P2014似乎有直接树形dp的做法,但我还是多叉转二叉做的。我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和...