钱数很少所以它也能压进状态裏。
还有向上贡献几个物品所以状态就是第 i 号物品,向上贡献 j 个总共花 k 元的当前就能得到的力量。
不同的是平常的树形dp该点的值就順便充当前 r 个子树的值;遍历完子树就完成自己的值。
但这里的状态里有一个“向上贡献 j 个”不太好弄。所以另开一个 g 只关注花叻多少钱和带来多少力量。
为了能用这个g转移到dp不出现花了某些钱其实买不够向上贡献的 j 个当前物品的情况,应该把“总共买 l 个当湔物品”放在最外面枚举
并且是倒序,为了沿用上一轮的g值
**不知为何,自己的代码比别人慢了好多!!我觉得没什么不同呀……以后再来看看吧
memset(g,-2,sizeof g);//g只和子树阶段、钱有关,因为dp涉及"向上贡献几个"所以不方便同时表示前几个子树的力量值