← 返回题单
题单练习 博弈
← 上一题 下一题 →

A5055 | 取石子（双端版）

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

太郎和二郎将进行以下博弈。

最初，他们面前有 $N$ 堆石子排成一排，每堆石子有 $a_i$ 个 。在取完所有石子之前，两位选手从太郎开始交替执行以下操作：

  • 取走开头或结尾的一堆石子。选手获得 $x$ 分，其中 $x$ 是被移除的石子的个数。

    • 假设 $X$ 和 $Y$ 分别是太郎和二郎在游戏结束时的总得分。太郎试图最大化 $X - Y$ ，而二郎试图最小化 $X - Y$ 。

    假设两位选手的选法都是最优的，请求出 $X - Y$ 的结果值。

    限制因素

  • 所有输入值均为整数。
  • $1 \leq N \leq 3000$
  • $1 \leq a_i \leq 10^9$

输入格式

输入内容由标准输入法提供，格式如下：

$N$
$a_1$ $a_2$ $\ldots$ $a_N$

输出格式

打印 $X - Y$ 的结果值，假定两位选手以最佳方式取石子。

输入输出样例

输入 #1
4
10 80 90 30
输出 #1
10
输入 #2
3
10 100 10
输出 #2
-80
输入 #3
1
10
输出 #3
10
输入 #4
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
输出 #4
4999999995
输入 #5
6
4 2 9 7 1 5
输出 #5
2
C++ 编辑器
输入
输出