Discrete Centrifugal Jumps(CFR669-D) - physics0523's 精進ログ

Discrete Centrifugal Jumps

長さ $n$ の数列 $h$ が与えられる。

$dp[1]=0\ ,\ dp[2]=dp[3]=...=dp[n]= \infty $ とする。

$i<j$ について以下の条件のいずれかを満たすとき、 $dp[j]=\min(dp[i]+1,dp[j])$ の遷移がある。

$j=i+1$

$\max(h_{i+1},h_{i+2},...,h_{j-1}) < \min(h_i,h_j)$

$\max(h_i,h_j) < \min(h_{i+1},h_{i+2},...,h_{j-1})$

$dp[n]$ を求めよ。

$2 \le n \le 3 \times 10^5$

$dp[i]$ からの遷移を考える。

明らかな遷移として、 $h[i] \le h[j]$ となる右に直近の $j$ と $h[i] \ge h[j]$ となる右に直近の $j$ には遷移がある。

では、そうでない場合、例えば $h=\{6,3,2,3,4,8\}$ のようなときの $dp[1]$ から $dp[5]$ のような遷移はどう検出するか…?

ここで、立場を入れ替えて考えてみる。(この立場の入れ替えが思いつけなかった…)

この相手側、具体例では $dp[5]$ から見て、 $h[j] \ge h[5]$ となる左に直近の $j$ が $j=1$ というわけである。

結局、全ての遷移について