Codeforces 319C Kalila and Dimna - Walkthrough

Reach tower $n$ with minimum cost. From tower $i$, jump to any $j > i$ with cost depending on heights. Rewrite: $dp[j] = \min_{i < j}(dp[i] + b_i \cdot a_j)$.

This is $\min(m_i \cdot x + c_i)$ where $m_i = b_i$, $c_i = dp[i]$, $x = a_j$. Lines have slopes $b_i$. If slopes are sorted, use deque. Otherwise, use Li Chao tree or sort offline. Query $a_j$ on the hull to get $dp[j]$. Add line $(b_j, dp[j])$ for future queries. Total: $O(n)$ or $O(n \log n)$.