A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are under construction and will be available soon. We get an array C of length N, where the value of C[i] describes the petrol station at location i in the following way:
- If C[i] = -1 there is no station.
- If C[i] = 0 there is a station at location i
- If C[i] = x there is a station at location i which will be
available at in x days.
Assume that flying from point a to point b takes no time. But if jet runs out of petrol on a point x of array, it should wait x days to refill and then continue its way. If x=-1, jet is stuck. The task is to find the minimal number of days the jet can get from point 0 to N+1, refilling on the way when necessary.
Is it a TSP variant with an extra condition? I am new to these.
P.S.The task is the same as "compute the maximum value of minimum values for each range of length R".
UPD. I looked at all types of dynamic programming questions, it is not close to them. I was given this problem in the university, as one in the miscellaneous set of problems.