白俊2579号:階段を上る

白俊2579号:階段を上る

アイデア

階段は一度に1段か2段上がることができます.この問題の厳しい条件「3つの階段を連続的に踏むことができず、最後の階段を必ず踏む」を満たすにはどうすればいいのでしょうか.
dpテーブルに対応する段差を踏むと、前の段差を含めて、得られた最大点数が保存されます.最後のレベルまでdp表に記入し、自然に「最後のレベルは必ず踏まなければならない」という条件を満たす.
最初の階段まで行くと、点数の最値は最初の階段の点数です.
2番目のステップに進むと、スコアの最値は1番目のステップと2番目のステップのスコアの和です.
3番目のレベルに進むと、スコアの最大値は、1番目のレベルと3番目のレベルの合計/2番目のレベルと3番目のレベルの合計のより大きな値です.

dp[0] = stairList[0]
dp[1] = stairList[0] + stairList[1]
dp[2] = max(stairList[0], stairList[1]) + stairList[2]

4段目から普及できます.N番目の階段を踏んだときに出られるのは2種類あります.
case 1. N−3段階段を踏むと分数の和(dp[N−3])+N−1段階段の分数+N段階段の分数
case 2. N-2級踏み込み時の分数の和(dp[N-2])+N級の分数

dp[N] = max(dp[N - 3] + stairList[N - 1] + stairList[N], dp[N - 2] + stairList[N])

この絵を見てください.
case 1では、(青)N-3段の階段を踏むと、dpテーブルに保存されていることがわかります.図には20+15=35が格納されている可能性があります.
case 2の場合(赤)、N-2段の階段を踏むと、dpテーブルに保存されていることがわかります.図には10+20+25=55が格納される.
したがって正解は55+20=75です.
このように2つのcaseに分けることで「連続して3つの階段を踏むことができない」という条件を満たすことができます.

コード#コード#

import sys
input = sys.stdin.readline

N = int(input())
stairList = [int(input()) for _ in range(N)]
dp = [0]*N

dp[0] = stairList[0]
if N > 1:
    dp[1] = stairList[0] + stairList[1]
if N > 2:
    dp[2] = max(stairList[0], stairList[1]) + stairList[2]
if N > 3:
    for i in range(3, N):
        dp[i] = max(dp[i - 3] + stairList[i - 1] + stairList[i], dp[i - 2] + stairList[i])

print(dp[N - 1])

おしゃべり

今までに解いたdp問題の中ではほとんど一番難しかった.これが情報オリンピアド小学校部の問題ですか?私は幼稚園に違いない.