ABC210 D National Railway
$ iと$ j, $ iと$ i'を固定する作戦が上手くいかない事に気づくと, 別の観点で考えてみたくなる. ここで, 面倒な条件であるマンハッタン距離を辺のコストとしてみる. 具体的には, 隣接するマスにコスト$ Cの辺を張る. すると, マンハッタン距離の条件が一気に扱いやすくなり, DPでこの問題を解くことができる.
$ dp_{i, j} := マス$ (i, j)を選ぶときの鉄道建設にかかる費用の最小値から, $ A_{i, j}を除いたもの とすると, $ dp_{i, j} = min(dp_{i - 1, j}, dp_{i, j - 1}, A_{i - 1, j}, A_{i, j - 1}) + Cのように遷移できる.
ただし, ここで注意すべき点がある. このDPでは, 左上から右下に行くパターンしか数えられず, 右上から左下に行くパターンを数えることができない. そこで, グリッド全体を180度回転(90度回転を2回することにより実装できる)させて同様のDPを行うことにより, この場合も考慮でき, 正しい答えを求めることができる.
よって, この問題を$ O(HW)で解くことができた.