codeforces #382 div 2 E. Ostap and Tree (树形dp)

题目链接

题意:将一棵树的若干点染成黑色,要求满足对于任何一个点u,至少存在一个距离其k以内的点v被染成黑色,问染色方案数。

思路:还没完全搞懂。。。记录一些idea…

qq%e5%9b%be%e7%89%8720161201213929

qq%e5%9b%be%e7%89%8720161201214138

 

参考题解

以及:该题解中说的children指的是子树全体。。。坑死好吗。。。坑了一晚上。。气啊。

 

定义状态f[i][j]:以i为根的子树中,能向上贡献j个单位/需要外界往内填补j个单位,方案数

如果是贡献,j为负数

转移的话,考虑不断合并子树,假如说当前处理x为根的子树

不妨把它的儿子按照输入顺序从左往右编号1~N
一开始到x的时候,初始状态f[x][-k] = f[x][1] = 1 
然后不断把儿子的信息合并给x
做法是x与儿子枚举每一个可能的j值然后判断一下这样的状态转移后如何,添加到辅助数组里
最后把辅助数组的值copy给f[x],,

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz