Can someone explain the solution in better way. I have read the tutorial but don't feel like getting it completely. Thank you. 1353E - K-periodic Garland
№ | Пользователь | Рейтинг |
---|---|---|
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 | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
Can someone explain the solution in better way. I have read the tutorial but don't feel like getting it completely. Thank you. 1353E - K-periodic Garland
Название |
---|
I did it in a slightly different way.
let dp[i] be the minimum number of ways substring s[1:i] can be k-periodic with the ith bulb switched on. Now while evaluating dp[i] we can face 2 situations.
2 If (i-k)th bulb is on, then
at each i I also considered the case that it can be the last bulb which is on and updated the ans accordingly.
ans = min(ans, dp[i] + (number of ways to switch off all the bulbs from i + 1 to n))
Step 1: Count the number of ones in the given string . Let it be "Ones" Step 2: Split the whole array into k different arrays, such that element i of the original array is now part of (i%k)th array . Now , we have to choose the best of these k arrays . Solving each array We need to find the starting and ending position in this array such that, the difference of ones and zeros is maximum in this range i.e. we need to set minimum number of 0s to 1s. Now, all we need is, number of 0s in this range + number of 1s outside this range + number of 1s in rest of the arrays (it can be counted with the help of "Ones", which we stored in step one. Here is the Implementation