恶心的式子，把上面拆开化一下得到好看的
\((\sum\limits_{i=1}^{n}x_i+1)^2\)
可以无脑\(dp\)一下
\(f[i][j]\)表示前\(i\)个数分了\(j\)段的最小代价
状态两维转移一维，\(O(n^3)\)拿头做
考虑第二维，发现好像可以\(WQS\)二分，对每一段额外增加一个价值，会使段数减少
此时复杂度\(O(n^2logn)\)
观察现在的\(dp\)式子：\(f[i]=min\{f[j]+(s[i]-s[j]+1)^2\}+mid\)
我们忽略掉常数\(mid\)，\(s[i]+1\)看作\(a_i,s[j]\)看作\(b_i\)，移项得到
\(f[i]-(s[i]+1)^2+2*s[i]*s[j]=f[j]+s[j]^2\)
我们吧\(s[j]\)看作\(x\)，\(f[j]+s[j]^2\)看作\(y\)，就可以斜率优化了
复杂度\(O(nlogn)\) 大胜利
原文：https://www.cnblogs.com/knife-rose/p/12616991.html