yukicoder No.595 登山

• 問題

問題概要

要素数Nの数列{a_i}とコストPが与えられる.
任意の場所へのワープにはコストP,隣接するiからjへのの移動にはmax(0,a[i]-a[j])かかる時,全ての点を訪れる最小コストを求めよ.
2 <= N <= 2*10⁵, 0 <= P,a[i] <= 10⁹

解法

1 普通のDP
解説が詳しい.
dp[i][j] := (iまでを全て回るコストで,jはそこが左に行く区間がどうか(0or1)) とすると,
dp[i+1][1] =min(dp[i][0],dp[i][1])+P(ワープしてくる),dp[i][1]+max(0,a[i]-a[i])(そのまま進む))
dp[i+1][0]も同様に遷移する.

2 RMQを使って高速化
iからjまで歩くコストをd(i,j)と書く.
この二方向の累積和を
Sl(i) = d(0,1)+d(1,2)+...+d(i-1,i)
Sr(i) = d(N,N-1)+...+d(i+1,i) として求めておく.
同様にDPの式を置くと,dp[i] は以下3つのminを取れば良い.
1.1回もワープせずにiまで歩く = Sl(i)
2.j<iなるjまでワープしj->iを歩く = dp[j] + P + Sl(i) - S(j)
3.j<iなるjまで来てiにワープしi->j+1を歩く = dp[j] + P +Sr(j+1) - S(i)
2.でワープせずにjまでくる方法もあるように見えるが,それは結局1.で余分に1回ワープしているだけなので切り捨てられる.
よって2,3のjに関する項をRMQのSegmentTreeに保存しておき,3つのminを取れば求められる.

メモ

最初 j = (i地点にいるか) としたが,それだと右から来た時ワープコストをどこに足せば良いかがわからなくなった.
解法は区間と考えることで最初にワープコストを足している.
その問題を書き出した上でうまく解決できるような状態の表し方を考察するようにしよう.

コード