Question

There are $N$ wooden boards arranged in a row from left to right, and $M$ craftsmen are tasked with painting these boards. Each board can be painted at most once. The $i$th craftsman can either choose not to paint or to paint a continuous segment of boards that includes board $S_i$ and has a length not exceeding $L_i$. For each board painted, the craftsman earns a payment of $P_i$. The $S_i$ values for different craftsmen are distinct.

What is the arrangement that maximizes the total payment earned by the craftsmen?

Solution

To implement the dynamic programming problem, it could be divided into two steps:

• State modelling: We need two variables to model the state: $\left(m,n\right)$ where $m$ donates the first $m$ craftsman and $n$ donates the first $n$ wooden boards.

• State transition: To find what previous states transit the current state $\left(m, n\right)$, we could divide the action that the $m$th craftsman performs

  • The $m$th craftsman paints no boards, which is corresponding to state $\left(m-1, n\right)$.
  • The $m$th craftsman paints some boards
    • It does not paint the $n$th board, which is corresponding to state $\left(m, n-1\right)$.

    • It paints the $n$th board. Because following the instruction, it must a continuous segment of boards, therefore, the indices of board that it could paint could be assumed to be $\left(k,n\right]$, which is corresponding to state $\left(m-1,\ k\right)$. Notice that the choice of decision variable $k$ must satisfy certain conditions

      • Board $S_m$ must be within the segment painted: $S_m\ \in\ \left(k,n\right]$.
      • The maximum length of the segment must be no more than $L_m$: $n\ -\ k \ \le\ L_m$.

      Therefore, we could be derive the system of inequalities that decision variable $k$ must satisfy

      $$ \begin{cases}k\ <\ S_m\ \le\ n\\n\ -\ k\ \le\ L_m\end{cases} $$

      This solves the range of $k$, donated as $\mathcal{D}\left(n\right)$, that could be choose: $\mathcal{D}\left(n\right)\ :=\ \left[n-L_m,\ S_m\right)$. Notice that the decision set $\mathcal{D}\left(n\right)$ changes with regards to state variable $n$.

  Therefore, the state transition could be derived

  $$ \begin{align*}\mathrm{dp}\left[m,n\right]\ =\ \max\left\{\mathrm{dp}\left[m-1,n\right],\ \mathrm{dp}\left[m,n-1\right],\ \max_{k\in \mathcal{D}\left(n\right)}\left\{\mathrm{dp}\left[m-1,k\right]\ +\ \left(n\ -\ k\right)\ P_m\right\}\right\}\end{align*} $$

Optimization

The naive solution takes $O\left(M\ N^2\right)$. To optimize, the code, we analyze both how the decision variable $k$ potentially calculate $\mathrm{dp}\left[m,n\right]$: $\mathrm{dp}\left[m-1,k\right]\ +\ \left(n\ -\ k\right)\ P_m$ and how the decision set $\mathcal{D}\left(n\right)$ changes with regards to state variable $n$. It should be noticed that variable $m$ is considered as the phase variable, which could be seen as a constant (such as $m$ and $P_m$)

• We rewrite the equation

  $$ \begin{align*}&\max_{k\in \mathcal{D}\left(n\right)}\left\{\mathrm{dp}\left[m-1,k\right]\ +\ \left(n\ -\ k\right)\ P_m\right\}\ =\ &\max_{k\in \mathcal{D}\left(n\right)}\left\{\mathrm{dp}\left[m-1,k\right]\ -\ k\ P_m\right\}\ +\ n\ P_m\end{align*} $$

  Notice that $n$ is not mingled with formula to be optimized: $\mathrm{dp}\left[m-1,k\right]\ -\ k\ P_m$. This guarantees that

  $$ \begin{align*}\arg\max_{k\in \mathcal{D}\left(n\right)}\left\{\mathrm{dp}\left[m-1,k\right]\ +\ \left(n\ -\ k\right)\ P_m\right\}\ =\ \arg \max_{k\in \mathcal{D}\left(n\right)}\left\{\mathrm{dp}\left[m-1,k\right]\ -\ k\ P_m\right\}\end{align*} $$

  Define $f\left(k\right)\ :=\ \mathrm{dp}\left[m-1,k\right]\ -\ k\ P_m$.

• Notice that when $n$ changes, the lower bound of $\mathcal{D}\left(n\right)$ would be increased by one and the upper bound of $\mathcal{D}\left(n\right)$ would stay constant. This implies the fact that each element would be inserted and erased from the data structure at most once: if there exists two decision $k_1<k_2$, where $f\left(k_1\right)\ \le \ f\left(k_2\right)$. It must hold that

  $$ \begin{cases}\forall n:\ k_2\ \in\ \mathcal{D}\left(n\right)\ \to \arg\max f\left(k\right)\ \neq\ k_1\\\exists n:\ k_1\ \not\in\ \mathcal{D}\left(n\right)\ \to\ k_2\ \in\ \mathcal{D}\left(n\right)\end{cases} $$

  Therefore, this implies when $k_2$ is inserted in the data structure, $k_1$ is no longer needed in the data structure. This reminds us to use the monotonic queue to solve the problem.

Implementation

#define F(k) (dp[m-1][(k)]-(k)*carp[m][1])
for(int m=1;m<=M;m++){
    deque<int>deq;
    for(int k=max(0,carp[m][2]-carp[m][0]);k<carp[m][2];k++){
        while(deq.size()&&F(deq.back())<=F(k))deq.pop_back();
        deq.push_back(k);
    }
    for(int n=1;n<=N;n++){
        dp[m][n]=max(dp[m-1][n],dp[m][n-1]);
        while(deq.size()&&n-deq.front()>carp[m][0])deq.pop_front();
        if(n>=carp[m][2]&&deq.size())dp[m][n]=max(dp[m][n],F(deq.front())+n*carp[m][1]);
    }
}

Notice, in this problem, when $n$ increases, only elements are removed from the decision set but no elements are added to the decision set, therefore, we could prebuilt the queue representing the decision set

deque<int>deq;
for(int k=max(0,carp[m][2]-carp[m][0]);k<carp[m][2];k++){
    while(deq.size()&&F(deq.back())<=F(k))deq.pop_back();
    deq.push_back(k);
}

Note that in the state space modelling $(n,m)$, we do not impose constraint on the condition that the $n$th carpenter must paint some segment or the $m$th segment must be painted by some carpenter. This implies that there is one trivial state transition: $\mathrm{dp}[n,m]=\max\{\mathrm{dp}[n-1,m],\mathrm{dp}[n,m-1]\}$. If $V^\star$ is the value obtained from the set representing the optimal solution using no more than $n-1$ carpenters to paint no more than $m%$ segments, $V^\star$ is also a feasible solution to the set representing using no more than $n$ carpenters to paint no more than $m%$ segments, and so is $\mathrm{dp}[n,m-1]$.