0 前置芝士 背包DP 多重背包 单调队列 1 多重背包问题 多重背包问题说的是:假设现在有 nnn 件物品和一个容量大小为 mmm 的背包,第 iii 件物品的体积为 viv_ivi​ ,价值为 wiw_iwi​,并且第 iii 件物品只有 sis_isi​ 件,现在要选择这些物品中的一些装进背包,请最大化背包里的物品价值总和. 一般的,如果不加任何的优化,那么我们可以令 fif

注:本文结合了一些 Drest 和 Targanzqq 的笔记和讲解内容,在此感激不尽. 0 一些前置芝士 线段树 1 什么是树链剖分 在大多数情况下,我们所说的"树链剖分"通常都是指的重链剖分. 众所周知,在处理序列问题上,我们有很多种方法,比如线段树,树状数组,平衡树… 那么,如何处理树上问题呢? 一种思路是将一棵树拍成一个序列(如dfs序),然后对序列进行操作.而树链