题解 | #[SDOI2016]征途#

首先方差的式子：

$S^2={\displaystyle \frac{1}{m}}{\sum }_{i=1}^m(\bar{x}-x_i{)}^{2}S^2=\backslash dfrac\{1\}\{m\}\backslash sum\_\{i=1\}^\{m\}(\backslash overline\{x\}-x\_i)^2$

$={\displaystyle \frac{1}{m}}{\sum }_{i=1}^m{\bar{x}}^2-2\bar{x}{x}_i+x_i^2=\backslash dfrac\{1\}\{m\}\backslash sum\_\{i=1\}^\{m\}\backslash overline\{x\}^2-2\backslash overline\{x\}x\_i+x\_i^2$

$={\displaystyle \frac{1}{m}}{\sum }_{i=1}^m({\displaystyle \frac{sum}{m}}{)}^2-2({\displaystyle \frac{sum}{m}})x_i+x_i^2=\backslash dfrac\{1\}\{m\}\backslash sum\_\{i=1\}^\{m\}(\backslash dfrac\{sum\}\{m\})^2-2(\backslash dfrac\{sum\}\{m\})x\_i+x\_i^2$

然后乘上$m^{2}m^2$

$=m{\sum }_{i=1}^m({\displaystyle \frac{sum}{m}}{)}^2-2({\displaystyle \frac{sum}{m}})x_i+x_i^2=m\backslash sum\_\{i=1\}^\{m\}(\backslash dfrac\{sum\}\{m\})^2-2(\backslash dfrac\{sum\}\{m\})x\_i+x\_i^2$

$=m\ast m\ast ({\displaystyle \frac{sum}{m}}{)}^2+m{\sum }_{i=1}^m-2({\displaystyle \frac{sum}{m}})x_i+x_i^2=m*m*(\backslash dfrac\{sum\}\{m\})^2+m\backslash sum\_\{i=1\}^\{m\}-2(\backslash dfrac\{sum\}\{m\})x\_i+x\_i^2$

$=su{m}^2+{\sum }_{i=1}^m-2sum{x}_i+m{x}_i^2=sum^2+\backslash sum\_\{i=1\}^\{m\}-2sumx\_i+mx\_i^2$

$=su{m}^2-2su{m}^2{\sum }_{i=1}^{m}m{x}_i^2=sum^2-2sum^2\backslash sum\_\{i=1\}^\{m\}mx\_i^2$

$=(m{\sum }_{i=1}^m{x}_i^2)-su{m}^2=(m\backslash sum\_\{i=1\}^\{m\}x\_i^2)-sum^2$

所以最后我们要最小化${\sum }_{i=1}^m{x}_i^2\backslash sum\_\{i=1\}^\{m\}x\_i^2$

套路枚举上一个断点。

$cc$是前缀和。

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

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

$dp[i][1]=c[i{]}^{2}dp[i][1]=\; c[i]^2$

于是90（!）pts了。

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

$dp[i][1]dp[i][1]$单独搞，考虑$dp[i][j]dp[i][j]$

$dp[i][j]=dp[k][j-1]+(c[i]-c[k]{)}^{2}dp[i][j]=\; dp[k][j-1]+(c[i]-c[k])^2$

$dp[i][j]=dp[k][j-1]+c[i{]}^2-2\ast c[i]\ast c[k]+c[k{]}^{2}dp[i][j]=\; dp[k][j-1]+c[i]^2-2*c[i]*c[k]+c[k]^2$

$2\ast c[i]\ast c[k]+dp[i][j]-c[i{]}^2=dp[k][j-1]+c[k{]}^{2}2*c[i]*c[k]+dp[i][j]-c[i]^2=\; dp[k][j-1]+c[k]^2$

设$x=c[k],y=dp[k][j-1]+c[k{]}^{2}x=c[k],y=dp[k][j-1]+c[k]^2$

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

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

于是仍然斜率优化（。

然后被卡精度了。

然后数据点分治。

然后过了、、、