[02579]階段を登る

[02579]階段を登る

質問する

階段を登るゲームは階段の下の起点から階段の先端の終点までのゲームです.図1>に示すように、階段ごとに一定の点数が書かれており、階段を踏むと階段の点数が得られます.
<図1>
<図2>に示すように、始点から、第1、2、4、6段の階段を歩いて終点に着き、合計10+20+25+20=75点となる.
<図2>
階段を登るには以下のルールがあります.

級は1回に1級または2級に上がることができる.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.

3つの連続した階段は、

も踏んではいけません.しかし、起点は階段には含まれていません.

最後に到着した階段は踏まなければなりません.
そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.

各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.

入力

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

しゅつりょく

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

コード#コード#

#include <iostream>
#include <algorithm> // reverse
#include <cstring> // memset

using namespace std;

/* 조건 */
#define MAX_N 301

/* 변수 */
int N;
int score[MAX_N], memo[MAX_N];

/* 함수 */
int dp(int idx) {
    if (idx >= N) return 0; // 범위를 넘어간 경우 (첫번째 계단)
    int& ret = memo[idx];
    if (ret != -1) return ret;
    return ret = max(score[idx] + dp(idx + 2), score[idx] + score[idx + 1] + dp(idx + 3));
}

int main() {
    /* 입력 */
    cin >> N; // 갯수 입력
    for(int i = 0; i < N; i++) { // score에 모든 점수 저장
        cin >> score[i];
    }

    /* 풀이 */
    score[N] = 0;
    memset(memo, -1, sizeof(memo)); // memo를 -1로 모두 전환
    reverse(score, score + N); // score를 거꾸로 저장

    /* 출력 */
    cout << dp(0) << endl;
}

解法

ろんり

このゲームでは、階段を踏んで歩く場合、以下の2種類があります.

の次の階段を踏んで飛び越える.

の次の階段を飛び越えます.

以上の2つのケースは、すべての階段が条件を守る場合にも適用されます.
このため、上記の2つの場合、より大きな値を選択して保存し、最後に最も高い値を見つけることができます.
しかし、最後の階段はいつも踏まなければならないので、逆関数で反対側から始めます.

へんすう

int N:段差数

score[]:階段数を格納する配列

備考[]:合成スコアを格納する配列

n.関数

int dp(int idx)

の範囲を超えている場合は、(idx>=N)0を返します.

値が

注記[idx](非-1)の場合、値

が返されます.

備考[idx]は、2つのケースでより大きな値

を格納する.

ソース

上位白駿[025799]レベル
https://www.acmicpc.net/problem/2579