写在前面
DP能力几乎已经退化到 (0) 了
部分题目是从同机房某神仙的提交记录里爬来的
线性DP
CF414B Mashmokh and ACM
Solution:
设 (f_{i, j}) 表示选了第 (i) 个数，当前最大的数位 (j)
显然有转移方程 (f_{i, j} = f_{i - 1, k}) ，其中 (k) 是 (j) 的因数
可以通过枚举 (k) 的倍数的方式来优化
P1280 尼克的任务
Solution：
设 (f_i) 表示 ([i,n]) 这段时间中的最长休息时间
如果当前没有工作，那么 (f_{i} = f_{i + 1} + 1)
否则，他必须选一个工作，(f_{i} = max{f_{i + a[j].ed}})，其中 (j) 是每项起始时间在 (i) 的工作
P5957 [POI2017]Flappy Bird
Solution：
直接在两个柱子间转移。
维护一个能到达的区间，到达下一个柱子会有一个能到达的最大值和最小值
然后和下一个柱子的区间取并即可。
发现坐标和一定是一个偶数，判断一下所在位置不合法的情况在稍微改变一下就行。
最后的答案？设点了 (x) 下，最终在 ((a,b)) 处，有
CF618D Hamiltonian Spanning Tree
Solution：
特判几个特殊情况。
然后用 路径中的点的度为2 去用 dfs 贪心，跑出最多选出的树边。
根据 Chen_怡 的代码自己yy了一道题（魔改），正解就是这份代码中的dfs函数
P4095 [HEOI2013]Eden 的新背包问题
询问很多，考虑把所有情况预处理出来。吸氧之后有 (80pts) 的好成绩。
设 (f_{i,j})，表示到第 (i) 个物品，用了 (j) 的容量。
从前面跑一边从后面跑一边预处理出来。
当询问第 (x) 个不能选时，就相当于把所有物品分成 ([1,x-1]) 和 ([x+1,n]) 两份。枚举分给两份的容量，然后在找出最大值就是答案。
附一句：这样做的极限复杂度是 (3 imes 10^8)，实际情况要快的多，大概是数据水？
CF864E Fire
普通的 01背包 变形，不用多想。
先对背包容量 (d) 排个序，然后照着跑就行了
选的方案可以直接用 ( ext{vector}) 存
注意最大的时间对应的答案不一定是最优的
P1450 [HAOI2008]硬币购物
容斥原理？
先跑个多重背包统计方案。令答案为 (f_{s})。
考虑只有一种硬币的情况
假设 (c_i) 限制数量 (d_i)，为了排除数量超出的干扰，可以在原来的基础上减去 (f_{s - (c_i * (d_i + 1))})
多枚硬币用类似的思想进行容斥就好了
P3188 [HNOI2007]梦幻岛宝珠
设 (f_{i, j}) 表示对于 (b) 为 (i) 的物品进行背包，当容量为 (j) 的时候的最大价值。
然后我们再设一个数组 (g[i][j]) 表示当使用 (b) 为 (0sim i) 的物品进行背包，(b) 为 (i) 的物品所占空间为 (j) 时，剩余物品（即 (b) 为 (1sim i-1)）所占空间为 (m&((1<<i)-1)) 的最大价值。
而这个 (m&((1<<i)-1)) 简单来说就是 (m) 的 (i) 位以下的值。
接着我们就可以考虑转移了，转移方程式如下：
那这个方程是什么意思呢？？
我们可以这样想，我们从 (j) 中拆除 (k)，拿给剩下的物品放。而高位向低位转移时会 ( imes 2)，然后再加上 (m) 中该位上的值 (（m>>(i-1))&1) 表示 (m) 在 (i-1) 位上的值）
最后我们只需要输出 (g[m 的位数][1]) 就可以了（因为 (m) 的首位一定是 (1)）