因为是最大值的最大值，所以可以变成每段选任意两个数做差，而不影响答案。状态只需要记录当前有多少段以及是否选了最大值/最小值。时间复杂度 $O(n^2)$。
（这个题有 $O(n\log n)$ 的加强版，但我忘了是哪场比赛了，做法是闵可夫斯基和/模拟费用流）
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 #282 for Problem #7067. The Great Wall
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 06:51:33
Last updated: 2025-12-14 06:51:37
题解
Comments
No comments yet.