AtCoder Beginner Contest 210 [ D - National Railway ]をPythonで解く（400点、💧水色diff）
問題
atcoder.jp 難しい問題。
解法
動的計画法で解く。
線路のコスト計算はC x (|i - i'| + |j - j'|)円。
この計算式から絶対値を外していく。
i' <= i, J' <= jとすれば
C x i - C x i' + C x j - C x j'
= C x i + C x j - C x i' - C x j'
= C ( i + j ) - C ( i' + j' )
駅の建設費用Aij, Ai'j'を加える
(Aij + C ( i + j )) + (Ai'j' - C ( i' + j' ))
真ん中で綺麗に独立した、i, jとi', j'に関する式に分けられた。
動的計画法を使い、dpをi, jで建設するもう片方の駅と線路の建設費(Ai'j' - C ( i' + j' )) の最小の値。
と定義する。
そのdpに(Aij + C ( i + j ))を足して、建設コストを出し最小のポイントを探す。
i' > iの点も考慮して数列Aを反転した数列で、もう一回動的計画法を計算する。
計算量O(2HW) 。
感想
色々と解説とコード読んで理解したとは思うけど、ムズカシイな。
これくらいの問題を自力で解ける日も来るのか！？
実装
snukeさんの解説動画内でのC++コードをPythonにコンバート。
