设 \(f_i\) 为将第 \(1\) 根和第 \(i\) 根柱子相连的代价，则有状态转移方程：?
我们可以令 \(sum_i=\sum\limits_{k=1}^iw_k\) ，这样就可以将 \(\sum\limits_{k=j+1}^{i-1}w_k\) 写作 \(sum_{i-1}-sum_j\) ，得：
展开 \((h_i-h_j)^2\) 得：
整理可得：
看上去是不是很像斜率优化DP的样子
虽然是李超线段树板子题，不过我们用斜率优化做
观察一下可以发现，若 \(i\) 确定，\((sum_{i-1}+h_i^2)\) 为常数项，可以忽略。
于是就变成了对于一个确定的 \(i\)，求 \(\min\{-2h_ih_j+f_j-sum_j+h_j^2\}\)
若决策 \(j\) 优于决策 \(k\) 则
化简得
即
令 \(Y(i)=f_i-sum_i+h_i^2,X(i)=2h_i\) ，则
因为 \(h_i\) 并不是单调的，所以需要CDQ分治来维护
用splay维护动态凸包也不拦你(因为我不会)
我们考虑将一个单调队列分为左右两个，然后递归处理，发现递归到长度为1时，可以像普通斜率优化一样建点。
回溯时，因为左边对右边会有影响，所以先将左边的状态插入单调队列，再更新右边的状态。
时间复杂度：\(O(n\log^2n)\)
P4655 [CEOI2017]Building Bridges
原文：https://www.cnblogs.com/jasony/p/13584331.html