# SUPW(ZCO'14)

http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-1b.php

How to create a dynamic programming solution to this zco problem?
After much efforts i was luckily able to solve the ipl problem but have got stuck on this problem. This looks similar to the ipl problem.
Any help will be highly encouraged.

``````Work[0..N] time for each workload
Best[j,0] means he does not work on day j
Best[j,1] means he does work on day j,not j+1
Best[j,2] means he does work on day j,j+1,not j+2

Initialize :
Best[N,0] = sum(Work[i],for all i from 0 to N-1)
Best[N,1] = sum(Work[i],for all i from 0 to N-1)-Work[N-1]
Best[N,2] = sum(Work[i],for all i from 0 to N-1)
Work=0

Now:
For j=N-1 to 0  j--
Best[j,0] = min(Best[j+1,0],Best[j+1,1],Best[j+1,2])
Best[j,1] = Work[j] - Best[j+1,0]
Best[j,2] = Work[j] - Best[j+1,1]
``````

Make a table on a paper and you’ll get it.

man simple speaking was unable to understand anything there… it was all messed up.
Could u tell me the logic! I’ll try to create the dp solution my self Well why would you use DP???

Isn’t the greedy method good here???

Nope. That gives the wrong answer majority of the times.

1 Like

Yeah It did now Can anyone tell me the recursive solution

If you solved IPL problem then just subtract your answer from total sum of array and you will get answer of SUPW problem. Check it out!!