can anyone explain how to solve warehouse problem of IEMCO6!
link to question—https://www.codechef.com/IEMCO6/problems/IEMCO6B
Let f(i) be the minimum cost for the subarray A_{1..i} such that A_i is not swapped with A_{i-1}.
Similarly, let g(i) be the minimum cost for the same subarray if A_i and A_{i-1} are swapped.
Then, figuring out a little gives the relations
\begin{aligned}
f(i) &= \min(|A_i - A_{i-1}| + f(i-1), |A_i - A_{i-2}| + g(i-1)) \\
g(i) &= \min(|A_{i-1} - A_i| + |A_i - A_{i-2}| + f(i-2), |A_{i-1} - A_i| + |A_i - A_{i-3}| + g(i-2))
\end{aligned}
These should make sense, but I can explain further if you want me to.
Of course the answer is simply \min(f(n), g(n)).
2 Likes
thanks bro!!
No problem 