8--D's blog

By 8--D, history, 8 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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.