MDantas's blog

Greedy Hydra
By MDantas, 11 years ago, In English

Hey, does anyone knows how to solve this problem ?

I'm doing some sort of Dynamic Programming on Trees, assuming that the answer when M > 2 is always the 'same'. So my DP is the follow:

  • DP[ has_fruit ][ node ][ K ]: What's the minimum answer when the subtree rooted at 'node' has exactly K nodes on the first group and the 'node' K has a fruit on it or doesn't have a fruit on it.

So I go down recursively on the tree calculating it for every node from the leaves to the root. And to compute DP[ has_fruit ][ node ][ K ], I'm using another DP that is very similar to the Knapsack DP.

Well, I'm sick and tired of getting WA's, so I decided to ask if anyone of you have already solved this one. My code: http://pastie.org/private/6gl337rrzkue0cxzokda

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

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it
  • In your main method, the condition to check for impossibility is wrong, check it again.
  • The root must always be chosen by the boss head.
  • In the solve2() method, you should be calling solve2(), not solve().
→ Reply