Saturday, September 5, 2009

BadNeighbors - 2004 TCCC Round 4 - TopCoder

Dynamic Programming

For simplicity you can calculate two different sets, one with all elements except the first and the other with all elements except the last one, cause the first and the last element can't be in the desired sequence. So now we have a linear sequence which we want to maximize the sum.
Suppose dp[i] is the maximum sum after checking the elements to position i.
dp[i] = max( element[i]+dp[i-2], element[i-1]+dp[i-3] )
What does it mean? The first (element[i]+dp[i-2]) means it's better to include element 'i' in the set and the second means it's better to include element 'i-1' in the set.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...