[CSP-S2019] 划分

朴素的 DP 是，设 $f_{i,j}$ 为 $a$ 长为 $i$ 的前缀，最后一处截断位于 $j$ 时的最小运行时间。

转移为

$$\displaylines{f_{i,j}=(s_i-s_j)^2\min_{s_k\le2s_j-s_i}f_{j,k} }$$

其中 $s_i=\sum_{j=1}^ia_j$。

不难发现 $f_{i,j}$ 在 $j$ 有意义的区间中单调不增。

考虑数学归纳法，$i=0$ 时成立。

设 $t_i$ 为长度为 $i$ 时所有合法的阶段方案中最后一个阶段位置的最大值。显然 $t_{i+1}\ge t_i$

假设单调性对于 $f_0,f_1,f_2,\cdots,f_{i-1}$ 均成立，考虑

$$\displaylines{\begin{aligned} f_{i,j+1}&=(s_i-s_{j+1})^2+f_{j+1,t_{j+1}}\\ &\le(s_i-s_{j+1})^2+f_{j+1,t_j}\\ &=(s_i-s_{j+1})^2+(s_{j+1}-s_{t_j})^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j-a_j)^2+(s_j-s_{t_j}+a_j)^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}-2a_j((s_i-s_j)-(s_j-s_{t_j})-a_j)\\ &=(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}-2a_j((s_i-s_{j+1})-(s_{j+1}-s_{t_j})+a_j)\\ &\le(s_i-s_j)^2+(s_j-s_{t_j})^2+f_{t_j,t_{t_j}}\\ &=(s_i-s_j)^2+f_{j,t_j}\\ &=f_{i,j} \end{aligned} }$$

由第二归纳法，单调性成立。

于是我们只关心 $f_{i,t_i}$ 的值。$t_i$ 具有单调性，可以双指针求得。