Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя 16it030

Автор 16it030, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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]) )

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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