出题人也是殚精竭虑不想写spj……

强行让工业区和商业区相邻也是醉了……

给跪了…（这题也能做？！！）

恍恍惚惚哼哼哈嘿红红火火蛤蛤蛤蛤蛤
顺便膜拜万古犇@Chenyao 的机器学习

这思路太机智了……

我无聊的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 :
经大神点拨重交了一遍就过了