Man, What Can I Say!
Lu_xZ
·
·
题解
纪念一下本人在校模拟用线段树优化dp单杀*900。
最小和最大没有本质区别，这里只讨论最小的情况。
设 f_i 表示前缀 i 的答案，显然是要枚举 j 使得 (j, i] 合并成一段：
f_i = \min \bigg(f_j + \lceil \dfrac{s_i - s_j}{x} \rceil\bigg)
其中 s_i = \sum_{i = 1}^i a_i。
想办法把 i, j 的贡献拆开，再用数据结构优化转移。
显然有 \lceil \dfrac{s_i - s_j}{x} \rceil = \lfloor \dfrac{s_i - s_j}{x} \rfloor + [s_i \not\equiv s_j \pmod x]，对于下取整，我们有广为人知的结论：
\lfloor \dfrac{s_i - s_j}{x} \rfloor = \lfloor \dfrac{s_i}{x} \rfloor - \lfloor \dfrac{s_j}{x} \rfloor - [(s_j \bmod x) > (s_i \bmod x)]
证明也很简单，对于三种不等关系讨论一下即可。
两者结合一下：
\lceil \dfrac{s_i - s_j}{x} \rceil =
\begin{cases}
\lfloor \dfrac{s_i}{x} \rfloor - \lfloor \dfrac{s_j}{x} \rfloor + 1 & (s_j \bmod x) < (s_i \bmod x)\\
\\
\lfloor \dfrac{s_i}{x} \rfloor - \lfloor \dfrac{s_j}{x} \rfloor & \text{otherwise}\\
\end{cases}
把所有 s_i \bmod x 离散化，用线段树优化转移即可。submission