Bob has $2$ cranes and $M$ available containers ($1 \leq C_i \leq M$) and he has to do $N$ transports from one container to another given an input list (the order of the transports must be respected).
To execute a transport from container $C_i$ to $C_j,$ Bob must choose a crane and move it to $C_i$, pick up the supplies, and then move it to $C_j$, where the crane remains until executing another transport.
The distance between two containers $C_i$ and $C_j$, is always $|i - j|$. We consider that each crane starts at the position of the first container it interacts with.
Since the cranes run on fuel, Bob would like to know, given the transport list, which crane to use for which transport, in order to conserve as much fuel as possible, by minimizing the total distance traveled by the two cranes. Print the minimum distance.
The input file, two_cranes.in, contains, on its first line, two numbers, $N$ and $M$, representing the number of transports Bob has to make, and the total number of available containers. On the next $N$ lines, it will contain one pair $[C_i, C_j]$ per line, representing the start and end positions for each container for the respective transport.
Example test:
$\text{3 10}$
$\text{2 4}$
$\text{5 4}$
$\text{9 8}$
Answer : $5$.
Explanation:
Arbitrarily start with crane 1 at position $2$ and travel to $4$. ($D_0 = | 2- 4| = 2$).
Proceed using crane 1 for the second transport as well. Note that the current position of crane 1 is $4$ (after completing the first transport). So now it travels to positon $5$ then to position $4$, for a total distance of $D_1 = |4 - 5| + |5-4| = 2.$
Finally, use crane 2 for the last transport, so the last distance is $D_2 = |9 - 8| =1$.
Hence, the final answer is $5 = D_0 +D_1 + D_2$.
My attemptS:
First of, I've mistaken this problem to be much easier than it is, hitting it with a straight greedy approach that seemed to fail a lot of test cases. I'd simply go along and choose the closest crane to the $C_i$ of the current transport and increment the distance with the appropriate cost.
Since this didn't work, I figured out that this should actually be solved using dynamic programming, but that's a particularly weak spot of mine. Initially, I found a very simple recurrence relation, but that only seemed to work on two test cases, so I guess it was dumb luck.
I would store a $dp[]$ int array, initialize it with $\infty$, then overwrite $dp[0]$ with the $C_i$ of the first transport. After that, I'd start from $i = 2$, process each transport and let $dp[i] = \min(dp[i - 1], dp[i - 2]) + cost(transport) + 1$ and finally output $dp[N]$.
Alas, this failed as well.
My last approach was trying to find some recurrence relation that I would later optimize using dynamic programming, but I couldn't actually put the pieces together for quite some time.
Data limits
$1 \leq N, M \leq 10^3$
$1 \leq C_i, C_j \leq M \text{ for every such pair}$
$C_i \neq C_j$ for every transport!
Time limits: C++ - $0.3s$, Java - $0.6s$
This problem is just practice, but the course I have it from doesn't give a solution. I've spent too much time on this already, I just want to know the solution, no hints please.
