please explain me the approach to solve the problem http://mirror.codeforces.com/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
please explain me the approach to solve the problem http://mirror.codeforces.com/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
Название |
---|
I didn't read editorial, but this is my solution :) Although, I don't think it will be different.
So your task is to find non-intersecting segments with length k and maximum possible sum. First think we can notice is, that seqments are always exactly of length k. So you can precompute sum of sequence [a, a + k - 1] for each a. This can be easily done with one traverse of array. When we knew sum for sequence [a, a + k - 1] just add element xa + k and subtract element xa and you obtain sum for sequence [a + 1, a + k].
Now we can fix some b. We know sum for [b, b + k - 1], but what about first sequence. Where is best possible a. Well, simply is the sequence [a, a + k - 1] with biggest sum and a + k - 1 < b. But we cannot process all such a, because we will get solution with time complexity O(n2).
But we can also precompute the best a for interval [0, i] for every i using dp. Again, if some Si is the biggest sum of some sequence of length k in interval [0, i], than max(Si, sum([i - k + 2, i + 1])) is answer for interval [0, i + 1]. And we already compute value of sum([i - k + 2, i + 1]) in first transition.
With all of this we just go through all possible b and pick Sb - 1 as the best position for a. You can check my implementation (with som comments) here: 4270931. Time complexity of this solution is O(n).
I hope this is clear enough. If you got any additional questions just ask :)