JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
TCCC 04 - Round 4 - Level One - BadNeighbors | Reply
Hi...

I'm new in DP.
I've read the tutorial about DP by Dumitru. In the Elementary part there are some problem for practice. I've try to solve the second one (BadNeighbors problem) but I couldn't solve it.

Here's problem statement link:
http://community.topcoder.com/stat?c=problem_statement&pm=2402&rd=5009

I don't have any idea about it. Please help me to get and solve it!
Thanks for your help.
Re: TCCC 04 - Round 4 - Level One - BadNeighbors (response to post by Blackwizard) | Reply
First, let's consider the easier problem where the town has arranged in a line.

f(X) is a maximum amount of donations that can be collected from residents 1,2,..X. (1 based)
Try to get the DP relation.

For the original problem, we have 2 choices for the first resident - either we choose or we don't choose.
1. If we decide to choose first resident we can't choose last resident since they're neighbor. So this problem is same as the residents 1..N-1 are arranged in a line.
2. If we don't choose first resident we can choose last resident. And this problem is same as the residents 2..N are arranged in a line.
RSS