UVa 10201

From Algorithmist
Jump to navigation Jump to search

10201 - Adventures in Moving - Part IV[edit]

Summary[edit]

You have to find the minimum cost for fuel to get from A to B without running out of fuel. Fuel can be bought from gas stations. Each station is has a distance from city A, and a cost for the fuel.

Explanation[edit]

We have to compute the minimum cost to get to city i with j litres of gas. For this we calculate d[i][j] - the cost required. Of course, d[0][100] = 0 (at first, the gas tank is half-full). To calculate d[i][j] we only need the city before (i-1). So

   d[i][j] = d[i-1][j+flost-fbought] + c[i]*fbought.
 where : - flost is the fuel neccesary to get from (i-1) to (i)
         - fbought is the amount of fuel bought from station (i)
         - c[i] is the gas cost at station (i)

For this, we have to iterate i from 1 to n+1, j from 0 to 200 and fbought from 0 to 200, resulting a complexity of ~40000n.

Gotchas[edit]

  • Any points one can easily overlook?
  • The correct way to understand ambiguous formulations?

Notes[edit]

  • Anything special to note about the problem.

Implementations[edit]

To make the implementation easier, we can consider the destination (B) as a gas station at which the gas cost is INFINITE.

Optimizations[edit]

Optimizations here.

Input[edit]

2

500
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399

600
100 9567
150 86
200 567
300 67
400 8
420 1
450 3

Output[edit]

450550

Impossible

References[edit]

  1. Reference 1

Categories here, use the form [[Category:UVa Online Judge|10201]] [[Category: Category Name]], see Categories for a list