Блог пользователя ss1073857

Help needed!
Автор ss1073857, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

it is better to drop problem link so that we can land over there.

→ Ответить