ABC040 C 柱柱柱柱柱解説 - hinamelプログラミングメモ

・N本の柱が立っており、i番目の柱の高さをaiとする。

・はじめ1本目の柱にいて、その次か2つ隣の柱のいずれかに飛べる。

・このとき、2本の柱の差の絶対値の分のコストがかかる。

・コストを最小化する。

・例えば棒1~4の4本があったとして、棒1から棒4に行くための最小コストを考えてみる。棒4には、棒2から1つ飛ばしで行くか棒3から行くかの2通りの行き方がある。この2通りの行き方のうちコストが小さいものが求めるべき値になる。

・さらに、棒3に行くための最小コストは、棒1から1つ飛ばしで行くか棒2から行くかの2通りの行き方があり、そのうちコストの小さい方が求めるべき値。棒2にいくための最小コストも同様に考えていく。

・このように考えると、以下の式が浮かんでくる:

棒[n+1]に行くための最小コスト =　

min(棒[n]にいくための最小コスト+n⇒n+1間のコスト,棒[n-1]にいくための最小コスト+n-1⇒n+1間のコスト)

・for文や再帰関数を用いるなどして、最小コストを1本ずつ求めていくと答えが得られる。

体感難易度:☆3

・dpに使う配列の要素数は少し多めにとる。

・dp[0]やdp[1]はfor文内に回さず、あらかじめ値を入れておく。

・配列の添え字を間違えないようにする。forはちゃんと0から始めたほうがバグらない