### ContestDestroyer's blog

By ContestDestroyer, history, 3 years ago, Recently I've come up with a problem:

Given $n$ bowling pins. It costs you $c_i$ to specially knock down the $i^{th}$ pin. Only when the $i^{th}$ pin is specially knocked down, a maximum of $l_i$ pins to its left and $r_i$ pins to its right will be normally knocked down. Find the minimum cost to knock down all the pins.

My initial thought is letting $\mathrm{F}_{i,\ j}$ be the minimum cost to clear all the pins from the $i^{th}$ to the $j^{th}$, and optimizing $\mathrm F$ in a manner similar to Floyd–Warshall, but I've not yet come up with a solid prove or decent solution based on this thought. Comments (2)
 » 3 years ago, # | ← Rev. 3 →   We can rephrase the problem as "given $n$ intervals $[a_i, b_i]$, you can knock down interval $[a_i, b_i]$ with cost $c_i$".It is a fairly classical dynamic programming problem now. You can start by defining $\mathrm{dp}[i]$ as the cheapest way to remove all pins up to the $i$-th. Initially, $\mathrm{dp}[i] = \infty$. Now, let's start processing the intervals in increasing order of the right coordinate. For an interval $[a_i, b_i]$ with cost $c_i$ you can update $\mathrm{dp}[b_i] \gets \min(\mathrm{dp}[b_i], c_i + \min(\mathrm{dp}[a_i - 1], \mathrm{dp}[a_i], \mathrm{dp}[a_i + 1], \ldots, \mathrm{dp}[b_i - 1]))$. $O(n^2)$ complexity is easy, $O(n \log n)$ is also possible.
•  » » 3 years ago, # ^ | ← Rev. 2 →   If the problem is rephrased like this, the order of knocking down intervals doesn't affect the result does it? Because in my initial problem as I understand, the order of knocking pins does affect the result.