If a trip from i to j is taxed, so is a trip from i-1 to j+1, i - 1 to j, and i to j + 1. We can use this to show that g[i][j] + g[i+1][j+1] <= g[i+1][j] + g[i][j+1]. Thus, the cost matrix is Monge.
A monge array can be shown to satisfy the Demidenko conditions. These conditions are necessary and sufficient conditions that a cost matrix should satisfy in order that the optimal tour be bitonic (first
This allows a DP solution, with state (i,j) which is the value of the optimal tour passing through all nodes between indices i to j. (Treat the optimal tour as two paths, one from 0 to n - 1, and the other from
There is also an O(n) solution to the problem too, once the g matrix is known. Each entry of the g matrix can be computed in O(log ^2 K) time using a data structure such as a segment tree. This leads to an
This question is marked "community wiki".
asked 28 Nov '12, 17:57