Codeforces 319C Kalila and Dimna - The DP

Let $dp[i]$ = minimum cost to reach tree $i$. Base: $dp[1] = 0$ (start here, no cost). Transition: $dp[j] = \min_{i < j}(dp[i] + b_i \cdot a_j)$. Naive: $O(n^2)$. For each $j$, try all $i$.

But look at the transition: $dp[i] + b_i \cdot a_j$. For fixed $j$, rewrite as $dp[j] = \min_i(b_i \cdot a_j + dp[i])$. This is $\min_i(m_i \cdot x_j + c_i)$ where $m_i = b_i$, $c_i = dp[i]$, $x_j = a_j$. That's CHT form!