UVa 10337

From Algorithmist
Jump to navigation Jump to search

10337 - Flight Planner[edit]

Summary[edit]

Given a field of windstrengths, you are to find the minimum cost to fly to the destination X. You can move climb, hold at the same height, or sink.

Explanation[edit]

This problem is similar to UVa 116 (Undirectional TSP) and is somewhat easier since it only wants the minimum cost. Do a dp from left to right to keep track of the minimum cost for reaching each position. Remember you are on a flight, so you have to land at X, i.e. at the last row (0 altitude according to the problem).

Gotchas[edit]

  • You must fly, literally, to the destination. So, you cannot play cheat by skimming through to destination at altitude 0 (plane driving on road?!). Keep the costs at every altitude 0 to be infinity as they are forbidden before the destination.

But if your code is not giving the right answers without altitude 0, let altitude 0 be part of the solution and see if it helps.

Input[edit]

2
 
400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1
 
1000
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9  
 7  7  7  7  7  7  7  7  7  7
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5
-7 -3 -7 -7 -7 -7 -7 -7 -7 -7
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9 

Output[edit]

120
 
354

See Also[edit]