题解

思路推导

若选择内部建筑 $i$ 作为酷建筑，至少需要增加 $c_i=\max(0,\max(h_{i-1},h_{i+1})+1-h_i)$ 层。两个相邻建筑不可能同时成为酷建筑，因此要在一条路径的内部位置中选择尽量多的不相邻点，并在数量最大时最小化代价和。

这是带二级目标的路径动态规划。每个状态同时记录已能得到的最大酷建筑数量和在该数量下的最小代价，比较时先比较数量，再比较代价。

做法

从左到右处理内部建筑，维护两个状态：当前建筑不选，以及当前建筑被选为酷建筑。选择当前建筑只能从上一位置未选的状态转移，并增加一座酷建筑和代价 $c_i$；不选当前建筑可以取上一位置两个状态中更优者。

处理结束后，在两个结尾状态中按相同规则取更优者，输出其最小代价。

正确性证明

对处理过的内部前缀归纳。未选状态涵盖所有最后一个位置未被选择的合法方案，因而可以由上一位置的任一最优状态转移；已选状态为了保持不相邻，只能由上一位置未选状态转移。两种转移恰好覆盖全部合法方案且不会生成相邻峰位。

状态比较先最大化选择数量，再在相同数量下最小化代价，所以归纳过程中不会丢弃可能导向更优最终答案的方案。处理完全部内部位置后，状态中的最大数量就是城市能达到的最多酷建筑数，对应代价即实现该数量的最小增加楼层数。

复杂度分析

每个内部位置只进行常数次状态转移，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。