convex_hull_trick

Base case: $dp[0]=0$. Each j < i contributes a line $f_j(x) = -2h[j] x + (h[j]^2 + dp[j])$. Starting line $L_0$ from $j=0$: slope $= -2 \cdot 0 = 0$, intercept $= 0^2 + 0 = 0$, so $L_0: y = 0$. The horizontal axis coincides with L0 for this base case.

Query $x = h[1] = 2$. Only $L_0$ is in the envelope so far, so $\min_{j<1} f_j(2) = L_0(2) = 0$. Therefore $dp[1] = h[1]^2 + 0 = 4 + 0 = 4$.

Insert $L_1$ for $j=1$: slope $= -2 \cdot h[1] = -4$, intercept $= h[1]^2 + dp[1] = 4 + 4 = 8$. $L_1: y = -4x + 8$. Note $L_1(2) = 0$, exactly where $L_0$ stands: $L_1$ joins the envelope from $x = 2$ onward.

Query $x = h[2] = 3$. $L_0(3) = 0$ and $L_1(3) = -4 \cdot 3 + 8 = -4$. The minimum is $L_1(3) = -4$. Therefore $dp[2] = h[2]^2 + (-4) = 9 - 4 = 5$.

Insert $L_2$ for $j=2$: slope $= -2 \cdot h[2] = -6$, intercept $= h[2]^2 + dp[2] = 9 + 5 = 14$. $L_2: y = -6x + 14$. Check: $L_2(3) = -4 = L_1(3)$. The new line touches the envelope at the next query point and becomes the winner for $x \ge 3$.

Query $x = h[3] = 4$. $L_0(4)=0$, $L_1(4)=-16+8=-8$, $L_2(4)=-24+14=-10$. The minimum is $L_2(4) = -10$. $L_2$ now dominates the envelope near the query. $dp[3] = 16 + (-10) = 6$.

Insert $L_3$ for $j=3$: slope $= -8$, intercept $= 16 + 6 = 22$. $L_3: y = -8x + 22$. Again $L_3(4) = -10 = L_2(4)$: the new line joins at the next query. Monotone slopes mean no line ever gets removed from the envelope in this input.

Query $x = h[4] = 5$. $L_0(5) = 0$, $L_1(5) = -12$, $L_2(5) = -16$, $L_3(5) = -18$. The minimum is $L_3(5) = -18$. $dp[4] = 25 + (-18) = 7$, the final answer.

Done. $dp = [0, 4, 5, 6, 7]$. The lower envelope (highlighted) consists of four pieces: $L_0$ on $[0, 2]$, $L_1$ on $[2, 3]$, $L_2$ on $[3, 4]$, $L_3$ on $[4, +\infty)$. Each CHT query at $x = h[i]$ drops to the current envelope in $O(\log n)$ total, so the DP runs in $O(n \log n)$ instead of $O(n^2)$. The classic application: Batch Scheduling, Train Plans, and CEOI 2004 Two-Sawmills.