【BZOJ 4182】Shopping

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4182
神犇题解：http://www.cnblogs.com/clrs97/p/4676134.html

解题报告

这个是一个多重背包，于是我们定义$f_{i,j}$为走到第$i$个点，花费$j$元的最大收益
我们先搞出一个DFS序，现在对于点$i$我们可以选或不选
若选，那么我们转移到DFS序的下一个去
若不选，那么我们需要跳过他的整个子树——这在DFS序上是一段连续的区间
于是我们就可以在$O(nm \log d)$的时间复杂度内解决这个问题了

另外Claris的点分的做法也非常好玩啊
通用性还要更强一点，提供了一种新的思路

—————————— UPD 2017.3.19 ——————————
这题今天写了写代码，似乎不能直接DP，会有一系列问题
将上述DP套个点分就没有问题了，不过套点分的话，就直接像Claris那么做就好啦
总之复杂度似乎还是只能做到$O(nm \log n \log m)$