16it030's blog

Could anyone help me get a better understanding for (267C) George & Jobs!
By 16it030, history, 4 years ago, In English

Hello, I am unable to figure out how I can formulate DP for this problem (https://codeforces.com/problemset/problem/467/C). Thank you!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can think it like this:

If you are at index i and you need x pairs, you have two options: 1) take the sum of the next m elements, move to index i+m and now look for x-1 pairs 2) move to index i+1 and look for x pairs

That can be written as a dp with two states: the index in the array and the number of pairs you need

dp[i][k] = max(dp[i+1][k], dp[i+m][k-1] + sum(A[i], A[i+1], ... , A[i+m-1]) )

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Okay, got it now... got confused with ranges(thought they could collide).. thanks for the help!

    → Reply