Hello, sadly I'm not in a good mood. Yesterday night I took part in SRM 559, which gave me a (-37) score, a reasonable low score due to a 0 point final score (I didn't solved any problem).
The problem set was harder than usual, with a dynamic programming problem in 250 DIV 2. The problem statement isn't available online due a bug in Topcoder site, so, the problem asks the highest column possible built using blocks of positive heights(of course).
1) With their indexes in ascending order.
2) A block with even height can't be built up a block with odd height.
Clearly a dp problem, I used all the time I could for reach a simple state for the dp but I didn't did it. After a bad sleep night and a wake up against my desire, I gave another chance for this problem, and finally found an winning stated which passed in the system tests.
Think of an a dp[i] which, dp[i] stands for the maximum height for a column ending which block[i];
The base case for a dp[i] is b[i], making it:
$dp[i] = b[i]$
Iterating over the 0 to i blocks, we first check the existence condition number 2 and them check, the maximum ending with b[i] block is dp[j] (column with maximum height ending with b[j]) + b[i] (height of the actual last block) making our state passage being like this:
$
dp[i] = max(dp[i], dp[j] + b[i])
$
The final code is this:
Feel free to ask some doubt or show your thoughts in the comments, for an editorial of 500 HyperKnight problem, check out vexorian Link awesome tutorial.
No comments:
Post a Comment