ss1073857's blog

Help needed!
By ss1073857, history, 4 years ago, In English

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

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply