Dynamic programming problem
Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.

Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations). 

Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that each car must be used at least once. If no feasible solution exists then $OPT[i,j] = + \infty$.

According to the above definition, you have $$OPT[1,j] = \begin{cases}
g(1, c_1) &amp; \mbox{if } j=1 \\
+\infty &amp; \mbox{if } j&gt;1
\end{cases}$$.

and, for $i=2, \dots, n$: 

$$OPT[i,j] = g(i,c_j)+
\begin{cases}
OPT[i-1, j] &amp; \mbox{if } j=1 \\
\min\{ OPT[i-1, j], OPT[i-1, j-1] \} &amp; \mbox{if } j&gt;1
\end{cases}.$$

The solution to your problem is $OPT[n,3]$, which can be computed in $O(n)$ time using dynamic programming.