首先方差的式子:

S2=1mi=1m(xxi)2S^2=\dfrac{1}{m}\sum_{i=1}^{m}(\overline{x}-x_i)^2

=1mi=1mx22xxi+xi2=\dfrac{1}{m}\sum_{i=1}^{m}\overline{x}^2-2\overline{x}x_i+x_i^2

=1mi=1m(summ)22(summ)xi+xi2=\dfrac{1}{m}\sum_{i=1}^{m}(\dfrac{sum}{m})^2-2(\dfrac{sum}{m})x_i+x_i^2

然后乘上m2m^2

=mi=1m(summ)22(summ)xi+xi2=m\sum_{i=1}^{m}(\dfrac{sum}{m})^2-2(\dfrac{sum}{m})x_i+x_i^2

=mm(summ)2+mi=1m2(summ)xi+xi2=m*m*(\dfrac{sum}{m})^2+m\sum_{i=1}^{m}-2(\dfrac{sum}{m})x_i+x_i^2

=sum2+i=1m2sumxi+mxi2=sum^2+\sum_{i=1}^{m}-2sumx_i+mx_i^2

=sum22sum2i=1mmxi2=sum^2-2sum^2\sum_{i=1}^{m}mx_i^2

=(mi=1mxi2)sum2=(m\sum_{i=1}^{m}x_i^2)-sum^2

所以最后我们要最小化i=1mxi2\sum_{i=1}^{m}x_i^2

套路枚举上一个断点。

cc是前缀和。

dp[i][j]dp[i][j]是前ii个切成jj段的最小值。

dp[i][j]=k=1i1dp[k][j1]+(c[i]c[k])2dp[i][j]= \min _{k=1}^{i-1}dp[k][j-1]+(c[i]-c[k])^2

dp[i][1]=c[i]2dp[i][1]= c[i]^2

于是90(!)pts了。

考虑如何过掉最后一个点。

dp[i][1]dp[i][1]单独搞,考虑dp[i][j]dp[i][j]

dp[i][j]=dp[k][j1]+(c[i]c[k])2dp[i][j]= dp[k][j-1]+(c[i]-c[k])^2

dp[i][j]=dp[k][j1]+c[i]22c[i]c[k]+c[k]2dp[i][j]= dp[k][j-1]+c[i]^2-2*c[i]*c[k]+c[k]^2

2c[i]c[k]+dp[i][j]c[i]2=dp[k][j1]+c[k]22*c[i]*c[k]+dp[i][j]-c[i]^2= dp[k][j-1]+c[k]^2

x=c[k],y=dp[k][j1]+c[k]2x=c[k],y=dp[k][j-1]+c[k]^2

于是就是一条斜率为2c[i]2c[i]的直线。

然后c[i]c[i]单调递增。

于是仍然斜率优化(。

然后被卡精度了。

然后数据点分治。

然后过了、、、