#AT12. Deque
Deque
[L] Deque(dp_l)
来源: AtCoder Educational DP Contest - Problem L 原题时限:2 秒 / 内存:1024 MB
题目描述
太郎与次郎用长度为 的数列 玩游戏。
初始时,数列 被放在一张桌子上。两人轮流进行如下操作,太郎先手:
- 从数列的开头或末尾取走一个元素。取出者获得该元素的数值作为得分。
设最终太郎的总得分为 ,次郎的总得分为 。太郎希望最大化 ,次郎希望最小化 。
假设两人都采取最优策略,求最终 的值。
输入格式
输入由标准输入按以下格式给出:
N
a_1 a_2 \ldots a_N
输出格式
输出两人均采取最优策略时 的值。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
4
10 80 90 30
输出:
10
样例 2
输入:
3
10 100 10
输出:
-80
样例 3
输入:
1
10
输出:
10
样例 4
输入:
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
输出:
4999999995
样例 5
输入:
6
4 2 9 7 1 5
输出:
2