一些 trick (7) | 加加减减的 dp 问题

· · 算法·理论

例题 1. CF626F

有 n 个学生，每个学生有一个正的能力值 a_i。现在要把这些学生分成一些(任意数量的)组，每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过 s 的分组方案总数，模 10^9+7。

先把 $a$ 排序。朴素的想法是 $dp_{i,j,k}$ 表示前 $i$ 个，有 $j$ 组没有分配完毕，目前末尾的加和开头的减一共贡献是 $k$ 的方案数。转移显然。转移中 $k$ 可以达到 $O(na_i)$，复杂度 $O(n^3a_i)$，无法通过。 注意到如果贡献是非负的，那么复杂度就是 $O(n^2k)$。考虑把 $\max-\min$ 转化成每一段差分的和。那么每一次转移多出来的值就是 $j$ 乘上差分。这样显然 $k$ 是不降的，于是复杂度 $O(n^2k)$，可以通过。 例题 2. [P9197](https://www.luogu.com.cn/problem/P9197) 将互不相同的 $N$ 个正整数 $A_1, A_2, \cdots, A_N$ 按照一定顺序排列。 假设排列为 $f_1, f_2, \cdots, f_N$，要求：$| f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| \leq L$。 求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。 $N\le100,A_i,L\le1000$。 将 $A$ 从小到大插入，就可以建模为连续段 dp 的模型。每个数根据左右是否有数就会有 $k\in\{-2,-1,0,1,2\}$ 倍的贡献。 发现这样一开始减很多后来再加很多就会导致贡献有 $O(NA_i)$ 种，乘上连续段 dp 的 $O(N^2)$ 就是 $O(N^3A_i)$，无法通过。 考虑像上题一样，把 $A_j-A_i$ 转化成差分的和。发现这样也是容易转移的。复杂度 $O(N^2L)$，可以通过。 已经加入 [一些 trick](https://www.luogu.com.cn/blog/483824/some-tricks)。