title: How to find the minimum cost fuel required to go from one place to another
body: <p>The question:<br> We want to go from a location to another which is D (D &lt;= 1,000,000,000) units away from it by truck. The truck can hold upto G (G &lt; 1,000,000) units of fuel and it consumes 1 unit of fuel for 1 unit distance. There are N (N &lt;= 50,000) fuel stations along the way. Every station i is X_i units away from the start and the price per unit of fuel is Y_i (Y_i &lt;= 1,000,000). We start the journey with B units of fuel. What is the minimum cost way to reach the destination? </p>
  
  <p>(<a href="http://usaco.org/index.php?page=viewproblem2&amp;cpid=283" rel="nofollow">Actual problem statement</a> from a USACO past contest)</p>
  
  <p>My algorithm:<br>
  Let F[i] = The minimum cost required to reach fuel station i and the N+1th fuel station is the destination.
  <br>Suppose k is the last station where we fill the tank before reaching i, <code>F[i] = F[k] + Y_k * (X_i-X_k)</code>. We try this for all the k &lt; i, such that <code>X_i-X_k &lt; D</code> and take the minimum one.<br> F[N+1] will be the final answer.</p>
  
  <p>The problems with this algorithm:<br>
  1. It will take O(N<sup>2</sup>) time which will not run within the time limits of 2 seconds.<br>
  2. It dosent consider the case where we reach a fuel station k with already m units of fuel and we only fill X_i-X_k-m units of fuel to reach i.</p>
  
  <p>How do I overcome these problems?</p>