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.

#### History

Revisions

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