Codeforces 319C Kalila and Dimna - Problem Statement

There are $n$ trees with heights $a_1, \ldots, a_n$ and costs $b_1, \ldots, b_n$. You start at tree 1 and want to reach tree $n$. From tree $i$, jumping to tree $j > i$ costs $b_i \cdot a_j$. Find the minimum total cost. The cost mixes $b_i$ (source) and $a_j$ (destination).

This product structure is the CHT signal. The problem statement specifies that heights $a_i$ are strictly increasing and costs $b_i$ are strictly decreasing. This ordering is exactly what CHT needs. Let me show you how to set up the DP.