工具包

可以看做自己的一些 tricks。

我觉得把 $tricks$ 称为 特征解法 更为恰当。

• 一段区间的转移相同
  把状态设为这段区间的价值和，然后容斥出这段区间对自己的贡献。

• dp 的贡献有正有负，考虑 费用提前计算 / 查分贡献
  例如 CF626F 计算极差：

  我们按升序排列，则极差表示为 $-a_l+a_r$。
  注意到 $-a_l+a_r=\sum \limits_{i=l+1}^{r} a_i-a_{i-1}$ ，差分计算即可。

• 贡献与相邻项有关，考虑 连续段DP。
  常见问法为 $|a_i-a_{i-1}|\leq d$，$\sum \limits_{i=2}^{n} |a_i-a_{i-1}|\leq d$, $|a_i-a_{i-1}|=d$ 等。

  在序列计数/序列极值中，如果当前元素的代价与两边的元素都有关，并且要求只能是重排，且首尾是容易计算的，我们可以考虑连续段 $DP$。
  一般的，设 $f_{i,j,k,l}$ 表示前 $i$ 个元素，现在有 $j$ 个段，当前代价为 $k$（如果有需要），两边的边界情况为 $l$(可能状压），然后按照某种顺序顺次插入元素，计算代价。
  基本操作类型为新开一段，接在某一段后面，接在某一段前面，合并某两段。
  某种顺序 的作用是让计算更为方便：
  $~~~~~~$ 1. 绝对值，极差：升序排列。
  $~~~~~~$ 2. 等不，不等于：同余。

• 基环树不一定要拆成环+树，可以看做 树+一条边。

  例题：[ICPC2019 WF] Hobson’s Trains

  通过一条边的贡献好算无比，可以大量减少码量。

• 多累物品权重一样，求最多可选多少个
  按照选取的代价从小到大排列，选一段前缀一定不劣。

• 两个背包同时选物品，判断能否装完。

  设 $f_{i,j}$ 表示前 $i$ 个物品，第一个背包用了 $j$ 的体积，第二个背包最小的使用体积。

• 线段覆盖可以看做从左端点向右端点+1连边，转化成图论问题。

  注意根据实际需求链接实际问题链接 $i$ $i+1$ 的 $0$ 权边。

• 修改有后效型，修改的量可以接受（比如单点修改）
  把一个点拆成若干个点，形如 $(u,t)$ ，表示第 $t$ 次修改的 $u$。

  一个点转移向自己时要特殊考虑

• 二分和cdq 都是去掉了 顺序带来的影响。