白俊2579号です.階段を登る

这是白俊2579号。登上阶段

분명 글을 써뒀는데 없어졌다...

1.質問

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

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

階段を登るには以下のルールがあります.

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

3つの連続した階段を踏んではいけない.しかし、起点は階段には含まれていません.

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

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

2.入力

入力された1行目に階段の個数が与えられる.

2行目から、一番下に1行ずつ置いた階段から、階段ごとに書いた点数を順番に与えます.階段の個数は300以下の自然数で、階段に書いてある点数は10000以下の自然数です.

3.出力

1行目に階段ゲームで得られる総点の最値をプリントアウトする.

4.解答

先ほど解きましたが、家に帰って文章を読むと覚えていません.

あ、最後の階段はよく踏んでいるので

n 2段目と不連続なラインで最低価格を探せばよい.

d[i-2], d[i-3] + arr[i-1]比較する.

さらにarr[i]を加えると、どちらも加算され、最後に加算される.

5.最初のコードと異なる点

先ほど解きましたが、家に帰って文章を読むと覚えていません.

こんな問題が出たのは初めてだったので難解だったようです.

次の問題の方が早い

6.コード

#include <iostream>
#include <algorithm>
using namespace std;

int stairs[300] = { 0 };
int d[301] = { 0 };

int main() {
	int k;
	cin >> k;

	for (int i = 0; i < k; i++) {
		scanf("%d", &stairs[i]);
	}

	d[0] = stairs[0];
	d[1] = stairs[0] + stairs[1];
	d[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

	for (int i = 3; i < k; i++) {
		d[i] = max(d[i-2], d[i-3]+stairs[i-1]);
		d[i] += stairs[i];
	}

	cout << d[k - 1] << endl;
}