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の方が早い。
コメント