### 8--D's blog

By 8--D, history, 8 months 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.

• +1

 » 8 months ago, # | ← Rev. 3 →   0 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.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 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.