此题我用暴力居然一分都没有啊
记 fi 表示考虑前 i 个建筑, 并且第 i 个建筑的高度不变的答案, 每次 转移时枚举上一个不变的建筑编号, 中间的一段一定变成相同的高度, 并且 高度小于等于两端的高度. 假设从 fj 转移且中间高度为 t, 则:
fi = ∑k=j+1i−1(t−hk)2+c(h[j]+h[i]−2t)
这样中间的高度可以 O(1) 求二次函数的对称轴天哪怎么能想出来啊确定。 考虑优化转移, 因为中间高度要小于两端, 所以最多只有一个 hj > hi 的 j 能够转移。 可以 维护关于高度的单调栈, 这样有效的转移次数就是 O(n) 的。
以下是标程：
``` cpp