Stair walking is a mission to reach the highest stair from the bottom. You must obey the following rules to get the scores shown on each stair:
1) You can go from the current stair to the next one or two stairs upward.
2) You should never step on all of the three consecutive stairs. (The starting point is not counted as a stair, however.)
3) You must step on the last stair.
For example, if you already stepped on the first stair, then you can go to the second or third one but not to the fourth one or step on both second and third
ones.
(At the starting location, you can select the first or second stair. In the following figure,
you can get up to 75 points.)
Obtain the max. scores you can get in the stair walking mission.
[INPUT FORMAT]
In the first line, the number of stairs N is entered. (1≤N≤300)
Starting with the second line, the scores for each stair P are entered. (1≤P≤10,000)
[Output format]
Display the max. scores earned from this mission.
Input/Output Example
Example 1
Input
6
10
20
15
25
10
20
Output
75
#include <iostream>
#include <vector>
using namespace std;
#define N 6
int input[N] = {10, 20, 15, 25, 10, 20};
int Solve(int n, int count) {
int sum1 = 0;
int sum2 = 0;
if (n == 0) return 0;
if (n == 1) return (input[0]);
sum1 = Solve(n - 2, 0);
if (count < 1)
sum2 = Solve(n - 1, count + 1);
return input[n - 1] + max(sum1, sum2);
}
int main() {
cout << Solve(N, 0) << endl;
return 0;
}