WQS二分

个人认为用导数理解更容易（虽然函数不连续，表达不够严谨）。

P4983 忘情

容易推得单段的权值为 \((\sum{a} + 1)^2\)。

\(O(mn^2)\)：\(dp(i, x) = \min\limits_{j = 0}^{i - 1}\left(dp(j, x - 1) + \left(\sum\limits_{l = j + 1}^{i}a_i + 1\right)^2\right)\)。

\(O(mn)\)：直接斜率优化。

上 WQS 二分：记 \(f(x)\) 表示划分成 \(x\) 段的最小权值。对于 \(f(x - 1) \to f(x)\) 的划分转移，权值的改变可以表示为 \((a + b + 1)^2 \to (a + 1)^2 + (b + 1)^2\)。其中 \(a, b\) 为之前同属一段，现在将其分开的权值。

\[\Delta = (a + 1)^2 + (b + 1)^2 - (a + b + 1)^2 = 1 - 2ab < 0 \]

所以 \(f(x)\) 为单减函数。\(x\) 增大时，贪心地选取 \(\Delta\)， \(ab\) 不增，所以 \(f^{'}(x)\) 为单增函数，\(f(x)\) 下凸。

令 \(g(x) = f(x) + kx\)，相当于每一段的权值加 \(k\)。\(g^{'}(x) = f^{'}(x) + k\) 可能在某处取到零点，此时有 \(g(x)\) 的最小值，记取得该最小值的极值点为 \(x_0\)，二分 \(k\)，若 \(x_0 > m\)，需使极值点左偏，\(k\) 增大；若 \(x_0 < m\)，需使极值点右偏，\(k\) 减小。

当 \(x_0 = m\) 时，直接对 \(g(x)\) 求最小值，则该最小值为 \(g(m)\)，且求该最小值时不用考虑划分段数的限制。回代可得 \(f(m) = g(m) - km\)。

求 \(g(x)\) 的最小值时可用斜率优化（并同时求出 \(x_0\)）：

记 \(dp_i\) 表示到第 \(i\) 个位置时的最小值，\(dp_i = \min(dp_j + (s_i - s_{j} + 1)^2 + k)\)。

化一下成这个形式：\(dp_i - (s_i + 1)^2 - k = \min(-2(s_i + 1)s_{j} + (dp_j + {s_{j}}^2))\)。

\(b = dp_i - (s_i + 1)^2 - k\)，\(slope = 2(s_i + 1)\)，\(x = s_{j}\)，\(y = dp_j + {s_{j}}^2\)。

随 \(x\) 增大，\(y\) 增大，同时 \(slope\) 不断增大，需要维护一个下凸壳。

斜率优化时必须判等，把同直线上的点给去掉。目前还没研究原理。

P5308 [COCI2018-2019#4] Akvizna

这里还是记目标段数为 \(m\)。给挑战者编号，按编号大小顺序依次打败，相当于转化成划分。

设 \(dp(i, x)\) 表示经过 \(x\) 轮打败前 \(i\) 名挑战者的最大价值，得到一个朴素的 dp 做法：

\[dp(i, x) = \min\limits_{j = 0}^{i - 1}\left( dp(j, x - 1) + \frac{i - j}{n - j} \right) \]

上 WQS 二分。记 \(f(x)\) 表示划分成 \(x\) 段的最大权值。还是来观察 \(f(x - 1) \to f(x)\) 的变化量。

比如把 \([a + 1, c]\) 划分成 \([a + 1, b], [b + 1, c]\)，则变化量为：

\[\Delta = \frac{c - b}{n - b} + \frac{b - a}{n - a} - \frac{c - a}{n - a} = \frac{c - b}{n - b} - \frac{c - b}{n - a} > 0 \]

所以 \(f(x)\) 为单增函数。每轮选 \(\Delta\) 最大的划分方式，选取之后该区间的子区间其划分后增量不大于 \(\Delta\)，且其他区间划分增量也不大于 \(\Delta\)，因此 \(\Delta\) 单调不增，\(f^{'}(x)\) 单减，\(f(x)\) 上凸。（这里只是简单说明了一下思路，核心只需证明子区间划分增量不大于 \(\Delta\) 即可。）

令 \(g(x) = f(x) + kx\)，每段权值加 \(k\) 后做无段数限制的 dp 求出全局最大值，并同时求出取得最大值的极值点 \(x_0\)。

二分 \(k\)，若 \(x_0 > m\)，需使极值点左偏，\(k\) 减小；若 \(x_0 < m\)，需使极值点右偏，\(k\) 增大。