ABC210 D - National Railway - oliverx3の精進記録

これコンテスト中に解けなかったのよくない

$H \times W$ のグリッドが与えられる。異なる $2$ 点 $(i, j), (i', j')$ を選ぶ。

$A_{ij} + A_{i'j'} + C(|i - i'| + |j - j'|)$ の最小値を求めよ。

$2 \leq H, W \leq 10^3$

$1 \leq C, A_{ij} \leq 10^9$

2 つ同時に動くと考えづらいので、1 点を固定する。

$i \gt i', j \gt j'$ を仮定すると絶対値がはずせる。 $(i, j)$ と $(i', j')$ を分離できるので嬉しい。

$A_{ij} + A_{i'j'} + C(|i - i'| + |j - j'|) = A_{ij} + C(i+j) + A_{i'j'} - C(i'+j')$

全ての $(i, j)$ について $A_{i'j'} - C(i'+j')$ の最小値を高速に求められれば良い。

$\mathrm{dp}_{ij}$ := $(i, j)$ についての $A_{i', j'} - C(i'+j')$ の最小値

と定義すると、 $\mathrm{dp}_{ij}$ は $\mathrm{dp}_{i-1j}$ と $\mathrm{dp}_{ij-1}$ の値を用いて $O(1)$ で求められる。（累積 min）

よって $O(HW)$ で解けた。 $i \gt i', j \gt j'$ を仮定していたことに注意する（A を反転させてもう一度同じように DP をすれば良い）

1 点固定はすぐに見えたが、この DP に至らなかった。ちゃんと式を書いて変数分離する。