[SDOI2012] 任务安排 / 任务安排
设 \(f_i\) 表示前 \(i\) 个任务的最小花费，发现转移时需要前一部分分的批数，存在后效性。
考虑在每次分出新的一批任务时计算其对之后所有任务的贡献，有转移：
其中 \(st_i = \sum\limits_{j \le i} T_j, sc_i = \sum\limits_{j \le i} C_j\)。
上式可以化简为：
斜率优化即可。
注意到每次查询的斜率不存在单调性，在单调栈上二分即可。
时间复杂度 \(O(n \log n)\)。
丝之割
可以发现，若数对 \(\left(u_0, v_0\right)\) 被除去，那么所有满足 \(u \ge u_0\) 且 \(v \le v_0\) 的数对均会被除去。
因此若将所有数对按 \(u\) 升序排列，那么剩余的有用的数对一定满足 \(v\) 严格递增。
这样之后每次消除数对一定是消除一个区间的数对，可以使用动态规划。
设 \(f_i\) 表示前 \(i\) 个数对的最小花费，那么有转移：
其中 \(u_i, v_i\) 表示第 \(i\) 个数对的两个数，维护出 \(a\) 的前缀最小值和 \(b\) 的后缀最小值即可。
这样转移式就可以化为斜率优化的形式，使用斜率优化即可。
CF1599F Mars
题意可以转化为询问一个区间是否可以重排为一段模 \(P = 10^9 + 7\) 意义下的等差数列。
设等差数列的首项为 \(A\)，区间长度为 \(n\)，若我们得到区间内数的和 \(S\)，那么根据等差数列求和公式：
我们可以得到 \(A\) 的表达式：
既然已经确定了公差，首项和长度，那么我们可以计算出该等差数列的每项的 \(k\) 次方和，以达到哈希的目的，再与原区间的 \(k\) 次方和比较即可。
考虑如何求出 \(k\) 次方和，可以发现其为：
可以使用二项式定理展开，得到：
\(\mathcal{O}(k)\) 计算即可。
CF713C Sonya and Problem Wihtout a Legend / 序列 sequence / CF13C Sequence / [USACO08FEB] Making the Grade G
若限制严格单调递增，可以将 \(a_i\) 均减去 \(i\)，这样我们只需要使得 \(a_i\) 单调不降即可。
设 \(f_{i, j}\) 表示使得前 \(i\) 个数符合要求，且第 \(i\) 个数为 \(j\) 的最小花费，有转移：
设 \(g\) 为 \(f\) 的前缀最小值，那么有转移：
考虑设 \(F_i(x) = f_{i, x}, G_i(x) = g_{i, x}\)，那么可以发现其均为关于 \(x\) 的凸函数，因此可以使用 Slopt Trick 进行优化。