把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

正文

分别是POJ1276 2392和3211
第一题是多重背包，题解是用二进制转化为01背包，即将可取ni次的wi物品分解为wi,2wi,4wi,…,(ni-2^k+1)wi个不同物品然后转化为01背包。
但个人不是那么解的，从下往上遍历已有的点，记录一个cnt表示这个点是已经拿取了cnt[i]个物品才得到的，这样的话当转移来源的cnt值等于ni就无法转移，也算是一种方法，不过只有在求存在性的时候可用，如果要求最优解，转化为二进制依然是不错的办法。
第二题还是多重背包，但是有个贪心策略需要排个序，由于ni最多只有10所以也不需要二进制转化了。
第三题是分组背包，用差值记录，虽然理论上时间复杂度不超过1e7但还是t了，转为用vector写，很快过了，说明是样例太多的问题。

在这里小记录一下背包的一些套路……
更新：
状压背包，类似商场优惠类题目，这里背包物品的重量可以是很多维，直接用循环去判非常恶心，所以使用状压直接减算，状压并不是压成二进制，而是根据维度的数量来压缩（如果有6件商品那就是6进制）。
限制背包，类似DIABLO III，每种物品只能选一个，并且可能会有其他条件但都可以转化过来，挺有意思。
数学背包，例如给一个数，求一种划分来使得所有数的lcm最大，实际上就是转化成素数的01背包来做。
依赖背包（树上背包），其实就是树形dp，但要记得遍历的时候从上到下并且起点要预留父亲的体积，返回值时要将预留出的这些体积也赋上值。