AIOJ

Example Introduction

「HNOI2008」Toy Packing

There are $n$ toys arranged in a row, and the value of toy $i$ is $c_i$ . We need to divide these $n$ toys into several segments. For a segment $[l,r]$ , its cost is $(r-l+\sum_{i=l}^r c_i-L)^2$ , where $L$ is a constant. Find the minimum cost of the partition.

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

The Naive DP Approach

Let $f_i$ denote the minimum cost of partitioning the first $i$ items into several segments.

State transition equation: $f_i=\min_{j [!note]+ Toy Packing (Modified)

There are $n$ toys arranged in a row, and the value of toy $i$ is $c_i$ . We need to divide these $n$ toys into several segments. For a segment $[l,r]$ , its cost is $(r-l+\sum_{i=l}^r c_i-L)^2$ , where $L$ is a constant. Find the minimum cost of the partition.

$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 the toy values may be negative. Continuing the previous approach, let $f_i$ denote the minimum cost of partitioning the first $i$ items into several segments.

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$ .

Apply the same transformation to the equation:

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

However, two conditions no longer hold:

The slopes of the lines are no longer monotonic;
The x-coordinates of the decision points added each time are no longer monotonic.

We still consider maintaining the convex hull.

When finding the optimal decision point, that is, when cutting the convex hull with a line, we replace finding the head of the monotone queue with binary search on the convex hull. We binary-search for the convex hull edge whose slope is closest to the line's slope, and thereby find the optimal decision.

When adding a decision point, that is, adding a point to the convex hull, we have two ways to maintain it.

The first is to maintain the convex hull directly with a balanced tree. Then the binary search for the decision point becomes a binary search on the balanced tree, and inserting a decision point becomes inserting a node into the balanced tree and deleting the points expelled from the convex hull. This approach is conceptually simple but cumbersome to implement.

Below we introduce an approach based on CDQ divide and conquer.

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

We first call $\text{CDQ}(1,mid)$ to compute $f_i,i\in[1,mid]$ . Then we build a convex hull from the decision points in this interval $[1,mid]$ and use this convex hull to update $f_i,i\in [mid+1,n]$ . At this point, the set of decision points is fixed. Unlike before, when decision points were added while computing DP values, we can first sort the $f_i$ for $i \in [mid+1,n]$ by the slopes $k_i$ of their lines, and then use a monotone queue to compute the DP values. Of course, DP values can also be computed by binary search on the static convex hull.
For every point in $[mid+1,n]$ , if its optimal decision lies in this interval $[1,mid]$ , it is updated to the optimal answer in this step. After this step, we find that all points in $[1,mid]$ have already played their full role, and whether they remain in the convex hull no longer affects subsequent answer updates. Therefore, we can discard the decision points in this interval and use $\text{CDQ}(mid+1,n)$ to solve the remaining problem in the right interval.

The 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 and other methods can optimize the computation of a DP equation and reduce complexity to some extent, but cannot change the equation itself.
The properties of a DP equation depend on the characteristics of the data, while the DP equation itself depends on the mathematical model in the problem.

Summary

Slope-optimization DP requires flexible application. Its purpose is to transform an optimization problem into a problem of finding an extremal intercept related to a convex hull in a two-dimensional plane. When an equation has unfavorable properties, data structures may sometimes be used to solve it; in that case, please consider the specific problem.

Slope Optimization

Example Introduction

The Naive DP Approach

Summary

Exercises