問題

コード

Submission #14018954 - AtCoder Beginner Contest 147

解法

左上のマスから右下のマスまで移動した際に、通ったマスに書かれている2つの数の差の絶対値を足すか引くかした値の絶対値を $x$ とすると、 $x$ の最小値を求めたい。

これは、マス $(i,j)$ までに $x$ の値を $k$ にすることができるかというbool値を $dp_{ijk}$ として管理すれば求めることができる。

遷移としては、 $dp_{ijk}$ がtrueの場合、次のマス（ $dp_{(i+1)j}$ または $dp_{i(j+1)}$ ）は、次のマスに書かれている2つの数の差の絶対値を $y$ とすると、 $k + y$ 、 $abs(k - y)$ 、 $abs(y - k)$ のときtrueとなる。