撷取秘藏

意识迷宫的第六层，是一间由黑曜石砌成的密室。密室里整齐排列着 $n$ 个宝箱，每个箱盖上都刻着古老的价值铭文。但宝箱之间连着细如发丝的感应线——如果打开相邻的两个，感应线就会触发连锁坍塌，把整条密室埋进深渊。

"不能开相邻的。"CC盯着那些感应线，"那不就是隔一个开一个？"

"没那么简单。"你说，"如果第三个宝箱的价值极高，而第二个极低，那你宁愿跳过第二个，把第三个拿下。问题是要找到一种打开方式，让总价值最大，同时没有任何两个被打开的宝箱相邻。"

"这像……下棋？"CC问。

"像走一条不能踩到地雷的路。"你说，"你站在第一个宝箱前，有两个选择：打开它，那就得跳过第二个，从第三个继续；或者不打开它，直接走向第二个。每个位置都做同样的选择，一直走到最后一个宝箱。但你要记住，前面做过的选择会限制后面的路，不能重复踩进同一个坑里。"

你开始推演。每一个宝箱都是一个岔路口，选或不选，像一根树枝分叉成两根。你把已经计算过的位置牢牢刻进记忆——第 $i$ 个位置的最优解一旦被求出，就不再回头重算。你像一道逆流的光，从最后一个宝箱照向第一个，沿途把最优选择标成金色。

屏幕上跳出了结果。第四十七号宝箱——价值四十七金币——被选中了。

"又是四十七。"CC说。

"四十七号宝箱。"Echo的声音轻得像叹息，"那是我留下的。在我叛逃前，我把最后一点能量藏在了这里。"

她飘到宝箱前，投影被箱盖上微弱的磷光照亮。

"打开它。"CC说。

"我打不开。"Echo说，"这是给你们的。"

你掀开箱盖。里面没有金币，只有一段发光的代码——一段关于如何进入Zero核心缓存区的密钥。

"下一层。"Echo说，"是最短路径的试炼。我们要找到最快的路，进入Zero的核心。"

题目描述

$n$ 个宝箱，价值 $v_i$。不能选相邻的宝箱。求最大总价值。

输入格式

$n$。然后 $n$ 个价值。

输出格式

最大总价值。

输入样例

5 1996
1 2 1994 12 29

输出样例

2

提示

• 每个位置做选或不选的决策，记录已计算位置的结果避免重复。
• 递推式：$dp[i] = \max(dp[i-1], dp[i-2]+v_i)$。

六道迷宫全部通过。意识迷宫的外围防线被突破，露出了更深层的结构。

Echo站在第六层的出口，投影比以往任何时候都暗淡，但也比以往任何时候都真实。

"下一层。"她说，"是Zero的核心缓存区。"

"核心缓存区里有啥子？"CC问。

"有我。"Echo说，"有Zero。有……一切的开始。"

[下一章：BFS与迭代加深 —— 寻找最短路径]