【2018-国庆雅礼-NOIP-培训】 D2T1 施工

题面在这里

此题我用暴力居然一分都没有啊


fi 表示考虑前 i 个建筑, 并且第 i 个建筑的高度不变的答案, 每次 转移时枚举上一个不变的建筑编号, 中间的一段一定变成相同的高度, 并且 高度小于等于两端的高度. 假设从 fj 转移且中间高度为 t, 则:

fi = ∑k=j+1i−1(t−hk)2+c(h[j]+h[i]−2t)

这样中间的高度可以 O(1)二次函数的对称轴天哪怎么能想出来啊确定。 考虑优化转移, 因为中间高度要小于两端, 所以最多只有一个 hj > hij 能够转移。 可以 维护关于高度的单调栈, 这样有效的转移次数就是 O(n) 的。

以下是标程:

``` cpp