Minimum cost to clear all the bowling pins.

Revision en2, by ContestDestroyer, 2020-03-05 07:16:38

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.


  Rev. Lang. By When Δ Comment
en2 English ContestDestroyer 2020-03-05 07:16:38 17
en1 English ContestDestroyer 2020-02-19 19:36:48 634 Initial revision (published)