階段を登る

今日の質問

https://www.acmicpc.net/problem/2579

階段を登る

もんだいぶんせき

の入力は10000まで300種類でint資料形式で十分で時間にも余裕があります.

前の結果が以下の内容に影響する場合は、DPを使用します.1格が3回を超えることができず、一番上の数に達することができれば、これもフィボナッチになることができます.

1ビンの結果と2ビンの結果が格納されます.1格に上昇した結果を保存する場合は、前の結果から2格に上昇した結果のみを採用します.

私の答え

#include <iostream>
using namespace std;
int n;
const int MAX = 300;
int score[MAX];

// 계단 오르기
int solution(){
    int t_score[MAX][2] = {0, }; // 한번, 두번으로 올라온것
    t_score[0][0] = score[0];
    t_score[1][0] = score[0] + score[1];
    t_score[1][1] = score[1];
    for(int i=2;i<n;i++){
        t_score[i][0] = t_score[i-1][1] + score[i];
        t_score[i][1] = max(t_score[i-2][0], t_score[i-2][1]) + score[i];
    }
    
    return max(t_score[n-1][0], t_score[n-1][1]);
}

別の解釈

#include<stdio.h>

int ar[302];
int D[302];

int main(){

	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&ar[i]);
		D[i]=D[i-3]+ar[i-1]>D[i-2]?D[i-3]+ar[i-1]+ar[i]:D[i-2]+ar[i];
	}
	printf("%d",D[n]);
	return 0;
}

学ぶべきところ

はよく1行に縮んでいます.DPで解くのは根本的に同じです.