Minimum cost to clear all the bowling pins.

Правка en2, от 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. Язык Кто Когда Δ Комментарий
en2 Английский ContestDestroyer 2020-03-05 07:16:38 17
en1 Английский ContestDestroyer 2020-02-19 19:36:48 634 Initial revision (published)