白俊2579号:階段を上る

質問する

題ショートカットキー>白俊2579号:階段を上る

に答える

これは3つの規則を持つ階段を上がることで得られる最大値を求める問題であり,dp(Dynamic Programming)で解くことができる.
初期化プロセスは次のとおりです.dp[1] = score[1]:最初の階段までの最大値はもちろんscore[1].dp[2] = score[1]+score[2]:第2レベルまでの最大値ももちろんscore[1]+score[2]です.dp[3] = max(score[1]+score[3], score[2]+score[3]):第3レベルまでの最大値は連続する3グリッドを超えてはならないため、score[1]+score[3]またはscore[2]+score[3]となる.
次の点火方式でdpを行えばいいです.max(score[i]+dp[i-2] , score[i]+score[i-1]+dp[i-3]):2級ジャンプ台or 1級ジャンプ台(連続3級xを踏む)

#include<iostream>
#define MAX 301
using namespace std;

int N;
int score[MAX], dp[MAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    // 입력
    cin>>N; 
    for(int i=1; i<=N; i++) cin>>score[i];
    
    // 초기화
    dp[1] = score[1];
    dp[2] = score[1]+score[2];
    dp[3] = max(score[1]+score[3], score[2]+score[3]);

    // dynamic programming
    for(int i=4; i<=N; i++)
        dp[i] = max(score[i]+dp[i-2] , score[i]+score[i-1]+dp[i-3]);
    
    // 정답 출력
    cout << dp[N];
}