精進2日目：DPコンテスト A-Frog1 - 競プロ引退しました。

A-Frog1 を自力で解けた

atcoder.jp

うんうん唸りつつ、自力で解けました。うれしい！

考え方

カエルさんが各足場に到達したときの、最小のコストを記録してあげればよさそうです。

足場を $h_i$ 、各足場でのコストを $C_i$ とすると、

$h_{1}$ にいるとき、 $C_1 = 0$
$h_{2}$ にいるとき、 $C_2 = |h_1 - h_2|$
$h_{3}$ にいるとき、 $C_3 = min(C_1 + |h_1 - h_3|, C_2 + |h_2 - h_3|)$
・・・
$h_{N}$ にいるとき、 $C_N = min(C_{N-2} + |h_{N-2} - h_N|, C_{N-1} + |h_{N-1} - h_N|)$ ←これが答え。

を愚直に実装すれば通りました。

Python3 で実装したコード

# coding: utf-8

def dp_flog(N, lst):
    lst_cost = [0] * N
    lst_cost[1] = abs(lst[0] - lst[1])

    for i in range(2, N):
        lst_cost[i] = min(lst_cost[i-2] + abs(lst[i-2] - lst[i]), lst_cost[i-1] + abs(lst[i-1] - lst[i]))
    return lst_cost

N = int(input())
lst_flog = list(map(int, input().split()))
print(dp_flog(N, lst_flog)[N-1])

実行時間 106ms、メモリ 13928 KB でした。

むすび

ほんとにこの実装で良いのかという自問自答はありますが、1月中は AC 取れたらどんどん先に進もうと思います。