Clever Frog

この解説では、各行動をこのように呼びます。

• 行動 $1$: 足場 $i\ (1 \le i \le N - 1)$ にいるとき、体力を $|h_{i+1}-h_i|$ 消費して、足場 $i+1$ へ飛び移る。
• 行動 $2$: 足場 $i\ (1 \le i \le N - 2)$ にいるとき、体力を $|h_{i+2}-h_i|$ 消費して、足場 $i+2$ へ飛び移る。
• 行動 $3$: 足場 $i\ (2 \le i \le N)$ にいるとき、体力を $C$ 消費して、足場 $i-1$ へ飛び移る。

この問題はEDPCに収録されている問題「Frog 1」と同様の問題です。 上記の問題と異なり、$1$ つ前の足場にも飛び移れるため、このままではDPの遷移を行えません。 しかし、以下の性質を使うことで遷移を前方向のみにすることができ、遷移を行うことができます。

• 消費する体力の総和を最小にする行動列（以降最適な行動列と呼ぶ）において、行動 $3$ の前後は両方とも行動 $2$ である。

この性質の正当性は以下のとおりです。

• 最初の行動は行動 $3$ になり得ない。（最初は足場 $1$ にいるため）
• 最後の行動は行動 $3$ になり得ない。（この行動を行った結果足場 $N$ にいるようにすることができないため）
• 行動 $3$ の前に行動 $1$ があるならば、これら $2$ つの行動を取り消すことで消費する体力の総和を減少させることができるので、最適な行動列ではない。
• 行動 $3$ の後に行動 $1$ があるならば、これら $2$ つの行動を取り消すことで消費する体力の総和を減少させることができるので、最適な行動列ではない。

この性質を用いて、行動 $3$ を以下に示す行動 $3'$ に置き換えることで、この問題を解くことができます。

• 行動 $3'$: 足場 $i\ (1 \le i \le N - 3)$ にいるとき、体力を $|h_{i+2}-h_i| + C + |h_{i+3}-h_{i+1}|$ 消費して、足場 $i+3$ へ飛び移る。（行動 $2,3,2$ の順にまとめて行う）

また元問題も同様ですが、各足場を頂点、可能な行動を重み付き有向辺とみることで、頂点（足場）$1$ から $N$ までの最短経路問題として解くこともできます。