Let us consider the problem where we need to quickly calculate the following over some set S of j for some value x.
Additionally, insertion of new j into S must also be efficient.
This will most likely be encountered with DP problems. For example, the recent problem 1083E - The Fair Nut and Rectangles from Round #526 has the following DP formulation after sorting the rectangles by x.
The problem requires quick calculation of the above define maximum for each index i. How can this be done?
Notice the special form of mj·x + cj. This is identical to the equation of a straight line with slope mj and Y-intercept cj. So the problem is equivalent to being given a set of lines and asked for the maximum y value any of those lines can give at a particular x. If you draw a bunch of straight lines on a plane, you'll notice that the maximum values are along what appears to be a convex hull.
- Every line on the hull provides the maximum value on some contiguous range of x values. Conversely, every line not on the hull is useless and never provides the maximum.
- All the lines on the hull have different slopes. The order of slopes also determines their position on the hull. A line with lower slope appears on the hull to the left of one with a higher slope.
So, a possible strategy can be to only maintain the convex hull and not keep the useless lines