众所周知，这道题有个结论：在合法的情况下，最优的答案的最后一段一定最小，所以DP的状态可以定义为哪一位结尾时最小，因为答案不是最小的状态最后一段肯定不是最小，可以把 $\Theta (n^4)$ 的裸DP 优化到 $\Theta (n^2)$ ，转移条件是当前这一段比上一状态的最后一段和小。

之后考虑把所有状态的最后一段的值组织成单调队列，可以证明不影响决策（从状态转移的角度思考），之后二分找最优决策点。

求证以上解法的正确性，以及这种写法是否可以进一步优化。