首先方差的式子:
S2=m1∑i=1m(x−xi)2
=m1∑i=1mx2−2xxi+xi2
=m1∑i=1m(msum)2−2(msum)xi+xi2
然后乘上m2
=m∑i=1m(msum)2−2(msum)xi+xi2
=m∗m∗(msum)2+m∑i=1m−2(msum)xi+xi2
=sum2+∑i=1m−2sumxi+mxi2
=sum2−2sum2∑i=1mmxi2
=(m∑i=1mxi2)−sum2
所以最后我们要最小化∑i=1mxi2
套路枚举上一个断点。
c是前缀和。
dp[i][j]是前i个切成j段的最小值。
dp[i][j]=mink=1i−1dp[k][j−1]+(c[i]−c[k])2
dp[i][1]=c[i]2
于是90(!)pts了。
考虑如何过掉最后一个点。
dp[i][1]单独搞,考虑dp[i][j]
dp[i][j]=dp[k][j−1]+(c[i]−c[k])2
dp[i][j]=dp[k][j−1]+c[i]2−2∗c[i]∗c[k]+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
于是就是一条斜率为2c[i]的直线。
然后c[i]单调递增。
于是仍然斜率优化(。
然后被卡精度了。
然后数据点分治。
然后过了、、、