因为是最大值的最大值，所以可以变成每段选任意两个数做差，而不影响答案。状态只需要记录当前有多少段以及是否选了最大值/最小值。时间复杂度 $O(n^2)$。
（这个题有 $O(n\log n)$ 的加强版，但我忘了是哪场比赛了，做法是闵可夫斯基和/模拟费用流）
QOJ.ac
QOJ
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.