Intro

Some DP (dynamic programming) problems have cost functions with absolute values: $|x - a_1| + |x - a_2| + \ldots$. The naive solution checks every possible value.

With large ranges, this takes too long. I'll show you how to represent these functions by their slope changes. You'll use priority queues to track breakpoints where slopes shift, avoiding computation of all values. By the end, you'll solve problems with ranges up to $10^9$ in $O(n \log n)$ time instead of timing out.