题目思路

题目抽象一下变成从数组中选出若干个不相邻的数，让这些数总和最大。

直接使用动态规划解决，$dp[i]$ 代表只考虑前 $i$ 个数得到的最大值，因为不能选相邻的数，所以 $dp[i] = max(dp[i-1], dp[i-2] + a[i])$， $dp[n]$ 就是最后的答案，发现 $a[i]$ 并不需要存下来，边更新边读入即可。

代码

C++代码

题目内容

在某个遥远的国度里，有一种传统的游戏叫做“跳跳棋”，这是一种基于积分的游戏。在这个国度里，跳跳棋已经有着悠久的历史，并且已经被许多人认为是一种智力和策略的游戏。人们在跳跳棋中可以锻炼自己的思维和判断能力。因此，这个游戏非常受欢迎，人们经常在闲暇时间里玩这个游戏。

传统的跳跳棋棋盘呈直线状，共有 $N$ 格，起始位置和结束位置都在棋盘之外。每一格都对应一个不同的积分值，而每次跳跃都必须跳过一个或多个格子，而且不允许跳到相邻的格子上，也不可以回跳，游戏的目标是通过跳跃来获取最高的积分。

输入描述

第一行为整数 $N$ ,表示跳棋格数 $(1 \leq N \leq 100000)$

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

输出描述

能获得的最高积分

样例

输入

3
1 5 2

输出

5