Step : Apply Aliens Trick. Add penalty per photo to remove the dimension. Now you have states instead of . Step : The transition has form where involves quadratic terms.
Rewrite in the form and apply Convex Hull Trick (from Section ). Final complexity: where is the coordinate range. The Aliens Trick removes one dimension, and CHT makes the remaining transitions fast. This combination is common in advanced DP.