vkditya0997's blog

Dynamic Programming ( Help )
By vkditya0997, history, 8 years ago, In English

Problem Statement : Click
I'm not able to arrive at the dp state.
But there were some comments on the announcement Post
It mentioned 

dp[ i ][ j ] = max( dp[ i ][ j - 1 ] , presum[ j ] - presum[ j - m ] + dp[ i - 1 ][ j - m ] );

Some one please explain this state?
Thank you

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Dp[I][j] = maximum sum of j non intersecting segments of length m from first I elements

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

dp[i][j] stands for what is the max value we can get when we reach the j th element and using exactly i pairs already.

If there is not a pair between element j — m + 1 and j (inclusively), then the value will be dp[i][j — 1].

Otherwise, if there is a pair chosen between element j — m + 1 and j, then the value will be: dp[i — 1][j — m] + (presum[j] — presum[j — m]) (which is the total sum of value in segment from j — m + 1 to j)

You can check my implementation based on the formula you provide.

http://www.codeforces.com/contest/467/submission/18229054

→ Reply