可以证明使得 $\sum s_i^2$ 最小的方案一定合法。假设不合法，则存在相邻两段 $(s_1,m_1)$, $(s_2,m_2)$ 使得 $s_1>s_2+\max\{m_1,m_2\}$。将分割点向右边移动一步，能使得 $s_1^2+s_2^2$ 严格变小，矛盾。
新的问题可以通过凸优化加凸包优化 DP 在 $O(n\log C)$ 的时间内完成。
QOJ.ac
QOJ
Discussion #355 for Problem #12220. Jealous Split
Type: Editorial
Status: Open
Posted by: jiangly
Posted at:
Last updated:
题解
Comments
No comments yet.