Блог пользователя themaskedhero

SGU — Mars Stomatology
Автор themaskedhero, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить