40 lines
1.1 KiB
Java
40 lines
1.1 KiB
Java
import java.util.*;
|
|
|
|
public class _2579{
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
int N = sc.nextInt();
|
|
int[] stair = new int[N+1];
|
|
for(int i=1; i<=N; i++){
|
|
stair[i] = sc.nextInt();
|
|
}
|
|
|
|
int[] dp = new int[N+1];
|
|
|
|
switch (N) {
|
|
case 1:
|
|
System.out.println(stair[1]);
|
|
break;
|
|
|
|
case 2:
|
|
System.out.println(stair[1]+stair[2]);
|
|
break;
|
|
|
|
case 3:
|
|
System.out.println(Math.max(stair[1] + stair[3], stair[2] + stair[3]));
|
|
break;
|
|
|
|
default:
|
|
dp[1] = stair[1];
|
|
dp[2] = stair[1] + stair[2];
|
|
dp[3] = Math.max(stair[1] + stair[3], stair[2] + stair[3]);
|
|
for(int i=4; i<=N; i++){
|
|
dp[i] = Math.max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]);
|
|
}
|
|
System.out.println(dp[N]);
|
|
break;
|
|
}
|
|
|
|
sc.close();
|
|
}
|
|
} |