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

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

Hello, can any one please tell how to solve This question

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

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

Firstly, sort the indices in chronological order. Secondly, we can define dp[i] as the maximum amount of money we can obtain at time a[i]. We can then say that this amount can be represented as the best out of these 2 values:

  1. We don't use interval i: the maximum amount of money we can obtain from a[i+1]...N

  2. We do use interval i: Define j as the first interval such that s[j] > e[i] (in other words, the first disjoint interval after i). Then, the value would be (the maximum possible money obtained from j..N) + p[i].

In terms of reccurence relation, this would be: dp[i] = max(dp[i+1], dp[j]+p[i])

This gives us an O(N^2) solution, which will definetly TLE. However, we notice that for all intervals i+1..N, there is always an interval j such that intervals i and j are disjoint, and that for all k from i+1..j-1, k and i are not disjoint. Therefore, we can binary search to find the value j. The total complexity therefore becomes O(NlgN)

My code

Hope this helped!

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

Please feel free to ask if anything is ambiguous.