一些 trick (8) | 连续段 dp

· · 算法·理论

例题 1. TopCoder 11213

给定 N 个正整数 R_i 和正整数 D，要求选择 N 个整数 0\le A_i<D，使得 \forall 1\le i,j\le N,|A_i-A_j|\ge R_i。求方案数模 10^9+7 的值。

不难发现如果我们钦定了 $A_i$ 的相对顺序（显然 $A_i$ 互不相同），则不难通过插板法算出方案数。此方案数之和 $A_i$ 相邻的 $\max(R_i,R_j)$ 的和有关。也就是，对于每个 $L$，我们要求出对于所有 $R$ 的排列 $R'$， $\sum\limits_{i=1}^{N-1}\max(R'_i,R'_{i+1})=L$ 的方案数。 考虑将 $R$ 从小到大插入 $R'$，维护目前的连续段，那么如果一个点若左/右已经有了一个点，那么会给左/右带来 $R_i$ 的贡献。令 $dp_{i,j,k}$ 表示前 $i$ 小的 $R$，目前有 $j$ 段，贡献是 $k$ 的方案数，容易求出新建一段/接在旁边/连接两段的转移系数。复杂度 $O(N^3R_i+D)$。 例题 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$。 考虑朴素的连续段 dp。发现此时两段的贡献和中间的贡献不一样。那么需要增加 dp 维数：$dp_{i,j,k,0/1,0/1}$ 表示前 $i$ 小的 $A$，连续段有 $j$ 段，贡献为 $k$，两端是否被占的方案数。转移略为复杂。 朴素的贡献是 $\{-2,-1,0,1,2\}A_i$，复杂度 $O(N^3A_i)$，无法通过。考虑差分优化状态即可做到 $O(N^2L)$。 已经加入 [一些 trick](https://www.luogu.com.cn/blog/483824/some-tricks)。 习题：[P5999](https://www.luogu.com.cn/problem/P5999)