# UVa 10337

## Summary

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

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

• 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

```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
```

```120

354

```