themaskedhero's blog

SGU — Mars Stomatology
By themaskedhero, history, 9 years ago, In English

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

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

State of the DP

Basically a dp[ current_gum ][ number_of_cured_teeth ].

I filled the DP from 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 teeth

To pass the time limit you must keep track of cured teeth in O(1). Adding a third dimension on the DP, with only 3 values, proved itself helpful.

Code

I something wasn't clear you can check the code I used, it has a lot of comments: Don't click me.

→ Reply