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

How To approach this DP problem
Автор ayush693, история, 3 года назад, По-английски

I am not getting any idea how to approach this problem Please help https://codeforces.com/problemset/problem/234/C

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

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

I used two-dimensional dp: dp[i][0] — if we continue negative sequence at index i dp[i][1] — if we continue positive sequence at index i

"state" is the number of changes needed to maintain a positive or negative sequence. Depending on the first element of the array we set base cases. Also, the last element of the sequence must be positive.

112223468

I prefer suffix-prefix sollution.

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

    In fact, you don't even need dp. You need need to count the number of less than or equal to 0 and greater than or equal to 0s. The rest is unnecessary, and it's total possible without DP.

    → Ответить