Hello, can any one please tell how to solve This question
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
Hello, can any one please tell how to solve This question
Name |
---|
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:
We don't use interval i: the maximum amount of money we can obtain from a[i+1]...N
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!
Please feel free to ask if anything is ambiguous.