def naive_cost(d, Cmax) :
price = 0
C = Cmax
current = d[0]
i = 1
while i <= len(d) :
if d[i-1]-current < C :
C -= (d[i-1]-current)
else :
price += (Cmax-current)**2
current=d[i-1]
C = Cmax
i+=1
return price
def _cost(lastStop, d, Cmax, i) :
if i == len(d)-1 :
return (d[i]-lastStop)**2
current = d[i]
next = d[i+1]
price = (Cmax-(lastStop-current))**2
#We have water left
if (next-lastStop) >= 0 :
return min(_cost(lastStop, d, Cmax, i+1), _cost(current, d, Cmax, i+1) + price)
#We don't have enough water we have to stop and refuel
price = 0
C = Cmax
current = d[0]
i = 1
while i <= len(d) :
if d[i-1]-current < C :
C -= (d[i-1]-current)
else :
price += (Cmax-current)**2
current=d[i-1]
C = Cmax
i+=1
return price
def _cost(lastStop, d, Cmax, i) :
if i == len(d)-1 :
return (d[i]-lastStop)**2
current = d[i]
next = d[i+1]
price = (Cmax-(lastStop-current))**2
#We have water left
if (next-lastStop) >= 0 :
return min(_cost(lastStop, d, Cmax, i+1), _cost(current, d, Cmax, i+1) + price)
#We don't have enough water we have to stop and refuel