刚进前500QAQ

整天就知道决策单调性，我没救了= =

一开始head初始化成0了，没发现，又推了一遍式子，恶心得要死要活的
不过斜率优化1A，爽

5000积分留念！

这个宏定义写的自己看着都醉。

第一发斜率优化

今天运气不错

回复 @<蒟蒻>刚铎 :

各种错误，while后面写了分号看不见...0.00.0

果然还是蒟蒻..

我讨厌所有有平方的题目= =
INF赋值总是不够
UPD:学了斜率优化后的第一题QAQ
果然求斜率的式子打错了真是做大死。。
还有注意到要开longlong了但是long long (int x)又是哪样啊(╯‵□′)╯︵┻━┻

没想到数形结合的题目这么难调试……手都冻僵了。。。。。
先确定是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)$。

为何N久之前写了一个优先队列。。而且每个点记录了一个决策区间 tail维护的时候二分队列最后一个点的区间- -这样也可以吧。。。。不过复杂度更高 是nlogn的吧。。

应当妥善考虑赋给决策“0”的坐标，以不影响凸包的性质

直接DP：20%，
AC：
从上一次决策开始枚举O（N）～O（N^2）：1s（总时间），
根据决策单调性减少决策枚举量O（NlgN）：0.2s
斜率优化：O（N）0.1s