ABC210 D - National Railway (400)
コンテスト中の考察
計算量を減らす方法が全く思いつかない
累積和みたいにしようとすると$ cによってうまくできない
全地点から全地点までのを求めると$ \mathcal{O}(H^2W^2)
解説の解法
$ dp[i][j] で(i,j)とそこより左か上の地点までに1個目を置いて今の地点まで線路を引いたときの最小コストとする
$ dp[i][j] = \min(a[i][j], dp[i-1][j] + c, dp[i][j-1] + c)
最小値はその点に二個目を追加したときの最小値
$ min(dp[i-1][j], dp[i][j-1]) + c + a[i][j]
左上から右下の方向でしか計算してないので左右反転してもう一度計算が必要