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

Автор vkditya0997, история, 9 лет назад, По-английски

How to solve this question using BIT?

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

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

It can be solved using dynamic programming. First use coordinate compression to get the values from 1...N Let dp[i][j] be number of subsequences of length j ending with i. Then, dp[i][j]=dp[i-1][j-1]+dp[i-2][j-1]+.....+dp[1][j-1];

This will take O(N*N*K) time.

Since a dp[i][j] is a cumulative sum of 0....i-1 we can use BIT for this purpose. We will have to make to make K BITs so that a particular state can be answered in O(logn) time. Complexity(O(N*K*logN))

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

There is a copy of this problem: 597C - Подпоследовательности, my solution using BIT: 15007060, Deemo's one: 14269844.

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