[AtCoder][DP][Educational DP contest]A-Frog 1

green frog AtCoder
Photo by Pixabay on Pexels.com

Educational EP Contest

Educational DP Contest - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

問題

A - Frog 1
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
問題キャプチャ。

方針

\(1\)次元のDPで。初期化はinfじゃなくても\(0\)で大丈夫。\(O(N)\)。

解答

#atcoder template
def main():
    import sys
    input = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n = int(input())
    h = list(map(int, input().split()))

    #output
    dp = [0]*n
    dp[1] = abs(h[1]-h[0])

    for i in range(1, n-1):
        dp[i+1] = min(dp[i-1]+abs(h[i+1]-h[i-1]), dp[i] + abs(h[i+1]-h[i]))

    print(dp[-1])

    #N = 1のときなどcorner caseを確認!
if __name__ == "__main__":
    main()

提出結果

Submission #31629354 - Educational DP Contest
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

Python3よりPyPy3の方が早い。

コメント

タイトルとURLをコピーしました