ACM Programming Question

This looks like a dynamic programming problem at first glance.

Basically, we have a function f(N,K) = the number of bannas brought home given K available bannas and the first N monkeys.

Clearly f(0,K) = 0 and f(N,0) = 0

Then all you have to do is figure out the value of f(n,k). You should do so by taking the maximum over two case:

1. The monkey doesn't take a bannana f(n,k) = f(n-1,k), since the monkey does nothing it is just like he isn't there
2. The monkey takes the bannana f(n,k) = f(n-1, k - Strength) + strength - stuff monkey eats

Fill a table our use memoization with this logic and then determine f(N,K) and you've got your answer.