我无聊的A了四次

没想到数形结合的题目这么难调试……手都冻僵了。。。。。
先确定是dp $$f(i) = \min_{0 \leq j < i} \{ f(j) + (S(i) - S(j) - L - 1)^2 \} $$
其中$S(i) = \sum\limits_{j =1}^i (C(j) + 1).$
然后把方程转化一下：$$f(i) = (S(i) - L - 1)^2 + \\ \min_{0 \leq j<i} \{-2(S(i)-L-1)S(j) + f(j) + S(j)^2 \}$$
就可以设$2(S(i)-L-1)$为斜率，$S(j)和 f(j) + S(j)^2$分别为横纵坐标建立凸包进行斜率优化，复杂度$O(NlogN)$.
最后可以发现每次对凸包进行二分查找时的斜率$2(S(i)-L-1)$是随i单调递增的……于是可以用单调队列优化到$O(n)$。

看我的超级BT版AC代码。题解的话，由于时间紧张，这周末应该能出完整版。
（@sea 我知道这是在讽刺我。。。）

单调队列个毛线~前缀和+后缀和小常数AC。

本题是出题人故意用堆优化Dijkstra去卡SPFA的……
那几个挂掉的提交都来自失败的SPFA作死尝试……
注意两点：①用vector存邻接表会RE（为何不是MLE？）②数据基本是随机生成的，也就是说步长一般会很大……所以Dijktra占便宜（把那两个点算出来就可以直接跳出），但SPFA+卡时WA了……

神犇们是什么做的

回复 @Asm.Def :
经大神点拨重交了一遍就过了

回复 @St.Burning\ : codevs

为什么我的代码得不到满分，请帮助

回复 @cstdio :
强烈呼吁萌帝把这题难度改为8星！！！

这个单文件5组数据，20s是为了吓人用的么……
出题人放学别走(╯‵□′)╯︵┻━┻
另外，必须一直坐电梯，不能在同层自由走动或者下楼……那个“下楼自行解决”的设定估计仅仅是为了世界观的严谨……

树链剖分维护“一段路径/DFS序列内的背包和”……

题解地址：
比例简化题解