归途致敬了这道题目
本质斜率优化DP板子题
推一下式子：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
已知：
s2=(v−v1)2+(v−v2)2+⋯+(v−vm)2ms^2 = \frac{(v - v_1)^2 + (v - v_2)^2 + \cdots + (v - v_m)^2}{m} s2=m(v−v1 )2+(v−v2 )2+⋯+(v−vm )2
然后：
s2=(∑i=1mvim−v1)2+(∑i=1mvim−v2)2+⋯+(∑i=1mvim−vm)2ms^2 = \frac{\left( \frac{\sum_{i=1}^m v_i}{m} - v_1 \right)^2 + \left( \frac{\sum_{i=1}^m v_i}{m} - v_2 \right)^2 + \cdots + \left( \frac{\sum_{i=1}^m v_i}{m} - v_m \right)^2}{m} s2=m(m∑i=1m vi −v1 )2+(m∑i=1m vi −v2 )2+⋯+(m∑i=1m vi −vm )2
展开：
s2=m×(∑i=1mvim)2−2×(∑i=1mvim)×(v1+v2+⋯+vm)+(v12+v22+⋯+vm2)ms^2 = \frac{m \times \left( \frac{\sum_{i=1}^m v_i}{m} \right)^2 - 2 \times \left( \frac{\sum_{i=1}^m v_i}{m} \right) \times (v_1 + v_2 + \cdots + v_m) + (v_1^2 + v_2^2 + \cdots + v_m^2)}{m} s2=mm×(m∑i=1m vi )2−2×(m∑i=1m vi )×(v1 +v2 +⋯+vm
)+(v12 +v22 +⋯+vm2 )
然后可化为：
s2=mm(∑i=1mvi)2−2×(∑i=1mvi)2m+(v12+v22+⋯+vm2)s^2 = \frac{m}{m} \left( \sum_{i=1}^m v_i \right)^2 - 2 \times \frac{\left( \sum_{i=1}^m v_i \right)^2}{m} + (v_1^2 + v_2^2 + \cdots + v_m^2) s2=mm (i=1∑m vi )2−2×m(∑i=1m vi )2 +(v12 +v22 +⋯+vm2 )
然后：
s2=−(∑i=1mvi)2m2+v12+v22+⋯+vm2ms^2 = -\frac{\left( \sum_{i=1}^m v_i \right)^2}{m^2} + \frac{v_1^2 + v_2^2 + \cdots + v_m^2}{m} s2=−m2(∑i=1m vi )2 +mv12 +v22 +⋯+vm2
还要 ×m2\times m^2×m2
s2×m2=−(∑i=1mvi)2+m×(v12+v22+⋯+vm2)s^2 \times m^2 = -\left( \sum_{i=1}^m v_i \right)^2 + m \times (v_1^2 + v_2^2 + \cdots + v_m^2) s2×m2=−(i=1∑m vi )2+m×(v12 +v22 +⋯+vm2 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
现在就可以发现，这个式子第一项是定值，只要求出第二项的右方式子的最小值。
用 fi,lf_{i,l}fi,l 表示前 iii 段分为 lll 天走的最小平方和
即有：
fi,l=min(fi,l,fj,l−1+(sumi−sumj)2)(0≤j<i)f_{i,l} = \min(f_{i,l}, f_{j,l-1} + (sum_i - sum_j)^2) \quad (0 \le j < i) fi,l =min(fi,l ,fj,l−1 +(sumi −sumj )2)(0≤j<i)
（mmm 可以最后乘上）
然后 80 分到手
考虑复杂度瓶颈，枚举 i,ji , ji,j 时间复杂度 O(n2m)O(n^2m)O(n2m) ，考虑压掉一个。
拆一下式子发现：
fi,l=sumi2+min(fj,l−1−2×sumj×sumi+sumj2)f_{i,l} = sum_i^2 + min(f_{j,l-1} - 2 \times sum_j \times sum_i+ sum_j^2) fi,l =sumi2 +min(fj,l−1 −2×sumj ×sumi +sumj2 )
显然，右边括号里部分是一个直线形式，其中
k=2×sumjk= 2 \times sum_j k=2×sumj
b=fj,l−1+sumj2b=f_{j,l-1}+sum_j^2 b=fj,l−1 +sumj2
其中斜率 kkk 单调递减
所以用单调队列维护一个下凸壳即可。时间复杂度 O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码变量和推导不同
