分类 dp
当状态分为几类，而且降维时每一类要降的维不一样，我们可以对每一类分别开 dp，用不同的状态设计达到优化目的。
CF2143D2 Inversion Graph Coloring (Hard Version) - 洛谷
构造交换器
在序列转换问题（即给定一些操作，让你把 \(A\) 序列变成 \(B\)）中，我们可以考虑如何构造交换器来解决问题。
AT_arc183_b [ARC183B] Near Assignment - 洛谷
构造：从极值调整
面对一些构造权值（题目有定义）为指定值的序列/树/图的题，可以先考虑权值最大或最小是什么情况，再慢慢调整到指定的权值。
CF2107E Ain and Apple Tree - 洛谷
拆贡献+枚举 last 操作
给你很多操作序列，让你求一个点在进行完每个操作序列后的最终位置和（每个操作序列后算一次答案）。
此时考虑枚举最终位置 \(pos\)，有多少个操作序列能到达 \(pos\)。
我们考虑枚举最后一次能到达 \(pos\) 的操作，然后把前后的操作一填就行。
CF2138D Antiamuny and Slider Movement - 洛谷
带权并查集维护基环树森林（有局限）
再次强调：有局限
把每个基环树的环随便断掉一条边，其他的放进带权并查集。
此时我们仅可以维护环长与加删边（可能需要线段树分治）。
CF2104G Modulo 3 - 洛谷
分段 dp
当最优解有明显的一段一段的时，可以直接从上一个断尾转移到下一个断尾。
CF2107F2 Cycling (Hard Version) - 洛谷
两数之积的欧拉函数
CF809E Surprise me! - 洛谷
杜教筛的另一用途
注：大写字母为前缀和函数，小写字母为原函数。
因为 \(H(n) = \sum_{d = 1}^{n} g(d)F(\lfloor n / d \rfloor)\)
所以当遇到形如右边的东西时就可以考虑此式子，可以直接把 \(O(10^k)\) 降到 \(O(k)\)（高精度开销）。
#6241. 性能优化 I - 题目 - LibreOJ
一个猜结论的方法与证明
当要构造一个序列时，我们可以猜相同的数在一起。
如何证明：如果 \(a_i, = a_j, i < j, \forall k \in (i, j), a_k \neq a_i\)，每个 \(k\) 放到外面都不劣，则结论成立。
按种类顺序操作
如果先一直执行一个操作，然后再一直执行第二个操作可以得到最优解，则这样做。
P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova - 洛谷
AT_arc195_d [ARC195D] Swap and Erase - 洛谷
又一个猜结论的方法与证明
当做一下让你进行操作然后求最小操作数的问题，可以考虑一个操作是否只能进行有限次（一般 \(1\) 次）。
如何证明：如果做更多次一定不更优，则这样做。
P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova - 洛谷
AT_arc195_d [ARC195D] Swap and Erase - 洛谷
树状数组优化数学
当式子中出现 \([f(x) \leqslant k]\)（\(k\) 为给定常数），且要对多个 \(k\) 求答案，此时我们可以对 \(k\) 排序，\(k\) 增加时，做一系列单点修改，查询时就是区间查询，直接用树状数组。
P3312 [SDOI2014] 数表 - 洛谷
\(\sum_{now \in a_i}\) 之类的式子
两种方法：
- 求出每个数的出现次数 \(c_i\) 然后改为枚举值域，中间乘一个 \(c_i\) 即可。
- 正常推，遇到一些限制时改为枚举集合，预处理出左右可能被枚举的集合即可。
P3911 最小公倍数之和 - 洛谷
\(\sum\) 与 \(\prod\) 的换位
P4152 [WC2014] 时空穿梭 - 洛谷