[白俊]2579号-階段を登る

5603 ワード
白駿 DP テキストリンク

📩 ソース


質問する


階段を登るゲームは階段の下の起点から階段の先端の終点までのゲームです.図1>に示すように、階段ごとに一定の点数が書かれており、階段を踏むと階段の点数が得られます.

<図2>に示すように、始点から、第1、2、4、6段の階段を歩いて終点に着き、合計10+20+25+20=75点となる.

階段を登るには以下のルールがあります.
  • 級は1回に1級または2級に上がることができる.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.
    • 3つの連続した階段は、
  • も踏んではいけません.しかし、起点は階段には含まれていません.
  • 最後に到着した階段は踏まなければなりません.
    • そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.
    各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.

    入力


    入力した最初の行には、階段の数が表示されます.
    2行目から、1行1つ、一番下の階段から、各階段に書いてある点数を順番にあげます.階段の個数は300以下の自然数で、階段に書いてある点数は10000以下の自然数です.

    しゅつりょく


    1行目に階段を登るゲームで得られる総得点の最値を出力します.

    👉 の意見を打診

  • dpを並べて、前からの階段に最大値を格納する点火式を以下のようにします.
  • dp[i] = max(dp[i-2] + lst[i], dp[i-3] + lst[i-1] + lst[i])
  • i段目の最大値までは、2칸 전 계단까지의 최대값 + i번째 계단의 점수および1칸 전 계단의 점수 + i번째 계단의 점수 + 3칸 전 계단ㅇ까지의 최대값の中でより大きな値になります.
    • n = int(input())
lst = [0] * 301
for i in range(n):
    lst[i] = int(input())
dp = [0] * 301
dp[0] = lst[0]
dp[1] = lst[0] + lst[1]
dp[2] = max(lst[0], lst[1]) + lst[2]

for i in range(3, n):
    dp[i] = max(dp[i-2] + lst[i], dp[i-3] + lst[i-1] + lst[i])

print(dp[n-1])
    Graphmsと次の接続.CMSパート3を見つける
    私が私が最初の次を終えるとき、私が学んだこと.JSプロジェクト