解题思路

题意可以抽象为：在一条长度为 N 的直线上，每个位置有一个非负分数，起点与终点都在棋盘外；每次“落子”到某格就获得该格分数，但不能从一格跳到相邻的格，也不能回跳。等价于从 N 个位置中选取若干个互不相邻的格，使得分数和最大。 这是经典的路径上加权独立集问题，也就是常说的 House Robber（打家劫舍） 动态规划。

设 dp[i] 表示考虑前 i 个格（下标 1..i）能取得的最大分数。 转移：

• 不选第 i 格：成绩为 dp[i-1]
• 选第 i 格：成绩为 dp[i-2] + a[i]

题目内容

现在有一种跳跳棋，跳棋路线有 $N$ 格排列为一条直线，起始位置和结束位置都在棋盘之外，跳到每一格上都可以获取一定的积分，但是不可以从一格跳到相邻的格，也不可以回跳，请回如何获取最高的积分。

输入描述

第一行为整数 $N$ ，表示跳棋格数 $(1≤N≤100000)$

第二行为每一格代表的分数 $M(1≤M≤1000)$

输出描述

能获得的最高积分

样例1

输入

3
1 5 2

输出

5

样例2

输入

4
5 2 4 9

输出

14