ABC040 C 柱柱柱柱柱

C 柱柱柱柱柱

N本の柱の高さが与えられる。i番目の柱をa_iとすると、一つまたは二つ隣の柱に飛び移るときにabs(a_i - a_i+1)またはabs(a_i-a_i+2)のコストがかかるとき、N番目の柱に着くまでにかかるコストの最小値を求めよ。

i本目の柱に着いた時の最小コストをdp[i]に入れることにすると、dp[i]はi-1番目とi-2番目の柱に着いたときのコストから以下のように求めることができる。

dp[i] = min(dp[i - 1] + abs(input[i] - input[i - 1]), dp[i - 2] + abs(input[i] - input[i - 2]));

なぜなら、i番目の柱に着いた時の最小コストはi-1番目の柱からi番目に飛び移るコストとi-2番目の柱からi番目に飛び移るコストのうち小さい方だからである。
これをdp[N-1]まで(0 originであるため)求めればそれが答えとなる。

同上

・求めたい値が漸化式で表せる(dp[i]やdp[i][j]がi,j以下の添え字のdpの要素で表せる)場合、DPができる。
・解が漸化式で表せないか考える癖をつけておくとよい？

・N本目の柱にたどり着くときのコストの最小値がN-1本目の最小値とN-2本目の最小値から求まること
・DP

特になし