You are given n switches, each switch connected to a led. cost of switch of switch i is ci. intially all leds are on. When any switch is used, all leds in range [i-k,i+k] will get toggled off (on to off, off to on). Find minimum cost to switch off all leds.N<=10000, K<=1000, Ci<10^9
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Use dp, where the state is the min-cost required till the index, and iterate over the previous k states and find the minimum, find the minimum using a sliding window, or some range data structure. For the given constraints you can find min the brute force way too.
it is better to drop problem link so that we can land over there.