可以证明使得 $\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
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #355 for Problem #12220. Jealous Split
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:15:58
Last updated: 2025-12-14 07:16:01
题解
Comments
No comments yet.