击鼓传花

题目描述

两个玩家在玩一个游戏，每个人的游戏目标是为自己夺取尽量多的分数。游戏一共有 $n$ 轮，每一轮游戏都对应一个分数，分数在游戏开始前就是给定的，记为 $a_1, a_2, \cdots, a_n$。

每一轮游戏中，手上有花的人可以做出选择：

• 她可以选择保留花。这样，这轮的分数就会送给对方，而到下一轮的时候，花仍在自己手上；
• 她可以选择取走这一轮的分数。这样，到下一轮的时候，花就是对方的，但这一轮的分数就是自己的；

游戏开始前，花在小爱手里。若双方都会使用最佳策略去尽量多得获得分数，那么小爱可以多少分数呢？

输入格式

第一行：单个整数 $n$

第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$

输出格式

单个整数：表示小爱获得的最大分数

数据范围

• 对于 $30\%$ 的数据，保证 $1 \leq n \leq 50$；
• 对于 $60\%$ 的数据，保证 $1 \leq n \leq 5000$；
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 200,000$；
• $1 \leq a_i \leq 10000$；

样例输入 #1

4
5 2 7 3

样例输出 #1

10

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布