Covered Walkway - Problem Statement

Cover $n$ points with roofs. Roof $[l, r]$ costs $c + (r - l)^2$. Find minimum total cost. $dp[i]$ = min cost to cover first $i$ points. Transition: $dp[i] = \min_{j < i}(dp[j] + c + (x_i - x_{j+1})^2)$. Expand the square.

After algebra: $dp[i] = \min((-2x_{j+1}) \cdot x_i + (dp[j] + c + x_{j+1}^2)) + x_i^2$. Lines have slope $-2x_{j+1}$ and intercept $dp[j] + c + x_{j+1}^2$. Apply CHT. Add $x_i^2$ to the query result.