| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Problem Statement : Click
I'm not able to arrive at the dp state.
But there were some comments on the announcement Post
It mentioned
dp[ i ][ j ] = max( dp[ i ][ j - 1 ] , presum[ j ] - presum[ j - m ] + dp[ i - 1 ][ j - m ] );
Some one please explain this state?
Thank you
Dp[I][j] = maximum sum of j non intersecting segments of length m from first I elements
dp[i][j] stands for what is the max value we can get when we reach the j th element and using exactly i pairs already.
If there is not a pair between element j — m + 1 and j (inclusively), then the value will be dp[i][j — 1].
Otherwise, if there is a pair chosen between element j — m + 1 and j, then the value will be: dp[i — 1][j — m] + (presum[j] — presum[j — m]) (which is the total sum of value in segment from j — m + 1 to j)
You can check my implementation based on the formula you provide.
http://www.codeforces.com/contest/467/submission/18229054