Skip to content

Slope Optimization

Example Introduction

「HNOI2008」Toy Packing

There are \(n\) toys, the \(i\)-th toy has value \(c_i\). These \(n\) toys need to be arranged in a row and divided into several segments. For a segment \([l,r]\), its cost is \((r-l+\sum_{i=l}^r c_i-L)^2\). Here \(L\) is a constant. Find the minimum total cost.

\(1\le n\le 5\times 10^4, 1\le L, c_i\le 10^7\).

Naive DP Approach

Let \(f_i\) denote the minimum cost to partition the first \(i\) items.

The state transition equation is: \(f_i=\min_{j<i}\{f_j+(i-(j+1)+pre_i-pre_j-L)^2\}=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}\).

Here \(pre_i\) is the prefix sum of the first \(i\) numbers, i.e., \(\sum_{j=1}^i c_j\).

The time complexity of this approach is \(O(n^2)\), which is insufficient for this problem.

Optimization

Consider simplifying the state transition equation: let \(s_i=pre_i+i, L'=L+1\), then \(f_i=\min_{j<i}\{f_j+(s_i-s_j-L')^2\}\).

Move terms independent of \(j\) outside, we get

\[ f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \} \]

Consider the slope-intercept form of a line \(y=kx+b\), rearranged as \(b=y-kx\). We express information related to \(j\) as \(y\), information related to both \(i\) and \(j\) as \(kx\), and the information to be minimized (related to \(i\)) as \(b\), i.e., the intercept. Specifically, set

\[ \begin{aligned} x_j&=s_j\\ y_j&=f_j+s_j^2\\ k_i&=-2(L'-s_i)\\ b_i&=f_i-(s_i-L')^2\\ \end{aligned} \]

Then the transition equation becomes \(b_i = \min_{j<i}\{ y_j-k_ix_j \}\). We treat \((x_j,y_j)\) as points on a two-dimensional plane, then \(k_i\) represents the slope of a line, and \(b_i\) represents the intercept of a line with slope \(k_i\) passing through \((x_j,y_j)\). The problem transforms into choosing an appropriate \(j\) (\(1\le j<i\)) to minimize the line's intercept.

slope_optimization

As shown in the figure, we translate this line with slope \(k_i\) upward from below until it touches a point \((x_p,y_p)\). Then we have \(b_i=y_p-k_ix_p\), and \(b_i\) attains its minimum. After computing \(f_i\), we add the point \((x_i,y_i)\) to the point set as a new DP decision. So, how do we maintain the point set?

It's easy to see that points that could minimize \(b_i\) must lie on the lower convex hull. Therefore, when searching for \(p\), we don't need to enumerate all \(i-1\) points; we only need to consider points on the convex hull. In this problem, \(k_i\) increases with \(i\), so we can maintain the convex hull using a monotonic queue.

Specifically, let \(K(a,b)\) denote the slope of the line passing through \((x_a,y_a)\) and \((x_b,y_b)\). Consider the queue \(q_l,q_{l+1},\ldots,q_r\), which maintains points on the lower convex hull. That is, for \(l<i<r\), we always have \(K(q_{i-1},q_i) < K(q_i,q_{i+1})\).

We maintain a pointer \(e\) to compute the minimum \(b_i\). We need to find an \(e\) such that \(K(q_{e-1},q_e)\le k_i< K(q_e,q_{e+1})\) (special handling is required when \(e=l\) or \(e=r\)). Then \(p=q_e\), meaning \(q_e\) is the optimal decision point for \(i\). Since \(k_i\) is monotonically increasing, the number of moves for \(e\) is amortized \(O(1)\).

When inserting a point \((x_i,y_i)\), we check whether \(K(q_{r-1},q_r)<K(q_r,i)\). If the inequality does not hold, we pop \(q_r\) until it is satisfied. Then we insert \(i\) at the tail of \(q\).

Thus, we have optimized the DP complexity to \(O(n)\).

To summarize the algorithm for the above slope optimization template problem:

  1. Enqueue the initial state.
  2. Each time, use a line \(f(i)\) related to \(i\) to cut the maintained convex hull, find the optimal decision, and update \(dp_i\).
  3. Add the state \(dp_i\). If a state (i.e., a point on the convex hull) is no longer on the convex hull after adding \(dp_i\), it needs to be removed before adding \(dp_i\).

Next, we introduce advanced applications of slope optimization, combining it with binary search/divide and conquer/data structures to maintain DP equations with less favorable properties (lacking some monotonicity).

Binary Search/CDQ/Balanced Tree Optimization for DP

When searching for the optimal decision at point \(i\), we use a line \(f(i)\) related to \(i\) to cut the convex hull we maintain. The point of tangency is the optimal decision.

In the above example, the slope of the line changes monotonically with \(i\). However, for some problems, the slope is not monotonic. In such cases, we need to maintain every node on the convex hull and then use the current line to cut the convex hull each time. This process can be solved using binary search because the slopes between adjacent points on the convex hull are monotonic.

Toy Packing Modified

There are \(n\) toys, the \(i\)-th toy has value \(c_i\). These \(n\) toys need to be arranged in a row and divided into several segments. For a segment \([l,r]\), its cost is \((r-l+\sum_{i=l}^r c_i-L)^2\). Here \(L\) is a constant. Find the minimum total cost.

\(1\le n\le 5\times 10^4,1\le L\le 10^7,-10^7\le c_i\le 10^7\).

The only difference between this problem and "Toy Packing" is that toy values can be negative. Following the previous思路, let \(f_i\) denote the minimum cost to partition the first \(i\) items.

The state transition equation is: \(f_i=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}\).

Here \(pre_i = \sum_{j=1}^i c_j\).

Applying the same transformation:

\[ f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \} \]

However, now two conditions no longer hold:

  1. The slope of the line is no longer monotonic;
  2. The x-coordinate of each newly added decision point is no longer monotonic.

We still consider maintaining the convex hull.

When searching for the optimal decision point, i.e., cutting the convex hull with a line, we replace finding the head of the monotonic queue with: binary search on the convex hull. We binary search for the edge of the convex hull whose slope is closest to the line's slope to find the optimal decision.

When adding a decision point, i.e., adding a point to the convex hull, we have two methods to maintain it.

The first method is to directly maintain the convex hull using a balanced tree. Then the binary search operation for finding the decision point becomes binary search on the balanced tree, and inserting a decision point becomes inserting a node into the balanced tree and deleting several points that are kicked out of the convex hull. This method is conceptually clean but cumbersome to implement.

Below we introduce an approach based on CDQ Divide and Conquer.

Let \(\text{CDQ}(l,r)\) represent computing \(f_i\) for \(i\in [l,r]\). Consider \(\text{CDQ}(1,n)\):

  • First, we call \(\text{CDQ}(1,mid)\) to compute \(f_i\) for \(i\in[1,mid]\). Then we build a convex hull from the decision points in the interval \([1,mid]\), and use this convex hull to update \(f_i\) for \(i\in [mid+1,n]\). At this point, our decision point set is fixed, unlike before where we added decision points while computing DP values. Therefore, we can first sort \(f_i\) for \(i \in [mid+1,n]\) according to the line slope \(k_i\), and then use a monotonic queue to compute the DP values. Alternatively, we can compute DP values by binary searching on the static convex hull.

  • For each point in \([mid+1,n]\), if its optimal decision position lies in the interval \([1,mid]\), it will be updated to the optimal answer in this step. After executing this step, we find that all points in \([1,mid]\) have served their purpose; their presence in the convex hull no longer affects subsequent answer updates. Therefore, we can directly discard the decision points from this interval and use \(\text{CDQ}(mid+1,n)\) to solve the remaining problems in the right interval.

Time complexity is \(O(n\log^2 n)\).

Comparing "Toy Packing" and "Toy Packing Modified", we can summarize the following two points:

  • Binary search/CDQ/balanced trees, etc., can optimize the computation of DP equations, reducing complexity to some extent, but they cannot change the equation itself.
  • The properties of the DP equation depend on the characteristics of the data, but the DP equation itself depends on the mathematical model in the problem.

Summary

Slope optimization DP requires flexible application. Its essence is transforming an optimization problem into an intercept extremum problem related to a convex hull on a two-dimensional plane. When encountering equations with less favorable properties, data structures are sometimes needed to assist in solving them, and the approach should be determined based on the specific problem.

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用