問題

https://atcoder.jp/contests/indeednow-finalb-open/tasks/indeednow_2015_finalb_d

考え方

$P_{(i,j)} \ge 0$ よりなるべく多くの点 $(i,j)$ に訪問することが最適であることがわかる。つまり全頂点に訪問する。また最大値を最小値と読み替えると、グリッドグラフ上で最小全域木を作ることができる。

各頂点に初めて訪問する場合に $P_{(i,j)}$ を点を得ることができる。全頂点には必ず訪問するので $\sum P_{(i,j)}$ 点は得ることができる。ま点 $(i,j)$ から $(i,j+1)$ または $(i+1,j)$ に訪問するときの移動ボーナスをグリッドグラフの辺として最小全域木を構築すると、最小全域木の和の最小値が求めたい解である。