Hi everyone,

http://acm.sgu.ru/problem.php?contest=0&problem=304

I was solving this problem and I was unable to. I believe that this is DP, but I do not know the state. I do note that, for any gum, we can easily uniquely determine how much it will cost to take n teeth from that gum by picking greedily.

Thanks much in advance, themaskedhero

Hi, I liked this problem, it's indeed solved using DP. That was my approach to it:

State of the DPBasically a

dp[ current_gum ][ number_of_cured_teeth ].I filled the

DPfrom left to right, top to bottom. For each gum you find the price of curing x teeth using the accumulated result of previous gum.That runs in

O(N*K).Keeping track of cured teethTo pass the time limit you must keep track of cured teeth in

O(1). Adding a third dimension on theDP, with only 3 values, proved itself helpful.CodeI something wasn't clear you can check the code I used, it has a lot of comments: Don't click me.