乘积压缩

qko-gym

 2021.04.02 21:10  2023.09.01 18:14  ACM  树形背包  乘积压缩  点分治 󰈭 2256字

Day1 hdu6643 因为例题不仅有点分治还涉及到了树上依赖背包的算法，才发现自己并不太会树形背包的若干优化算法，故学习。树形背包模板题给出一颗依赖树，询问总重量限定下可能获得的最大价值。物品的数量和重量的限制均不超过100 有不同的做法，复杂度也不同。向上合并随意采取$O(nm^2)$的算法即可在树上合并。 ...