The Small Castle Built by a Dwarf

Let $F_i(h)$ be the minimum cost for the first $i$ castles when the last height is $h$. Then

$$F_i(h)=\mathrm{cost}_i(h)+\min(F_{i-1}(h-1),F_{i-1}(h+1)).$$

Separate heights by parity and write $h=2x+p$. For each parity, $F_i$ is a discrete convex function. Taking the minimum of the two neighboring previous states becomes a length-one sliding minimum of a convex function, which is supported by shifting the two lazy offsets in slope trick.

The adjustment cost is convex as well. If $H_i-p$ is even, add two asymmetric V-functions at the same vertex. If it is odd, add one at each of two neighboring vertices. This reproduces the exact cost on $h=2x+p$. Enforce positive heights using a lower-bound penalty whose weight is larger than the sum of all genuine cost slopes.

A weighted two-heap slope-trick structure processes every breakpoint in logarithmic time. The total complexity is $O(N\log N)$. Use 128-bit integers for costs.