2799: T4-暗渡陈仓
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
33DAI 和 Kitten 正在玩一款游戏。游戏中有 $n$ 个城市，从左到右编号从 $1\sim n$，编号为 $i$ 的城市有 $a_i$ 的资源。
- 33DAI 一开始在城市 $1$，Kitten 一开始在城市 $n$。
- 游戏轮流进行，33DAI 先操作，Kitten 后操作。两人所在城市相邻时游戏结束。
- 假设 33DAI 在城市 $i$。轮到他操作时有两种操作方法：他可以选择可以走到城市 $i+1$；或者如果 Kitten 不在城市 $i+2$，就可以绕过城市 $i+1$，暗渡走到 $i+2$。
- 假设 Kitten 在城市 $i$。轮到她操作时有两种操作方法：她可以选择可以走到城市 $i-1$；或者如果 33DAI 不在城市 $i-2$，就可以绕过城市 $i-1$，暗渡走到 $i-2$。
- 游戏最终的评分为“**33DAI 走到的所有城市的资源值之和**”减去“**Kitten 走到的所有城市的资源值之和**”的数值。
- 33DAI 的游戏目标为最大化最终评分，Kitten 的目标为最小化最终评分。
假设两个人都足够聪明，请你输出最终评分会是多少。
- 33DAI 一开始在城市 $1$，Kitten 一开始在城市 $n$。
- 游戏轮流进行，33DAI 先操作，Kitten 后操作。两人所在城市相邻时游戏结束。
- 假设 33DAI 在城市 $i$。轮到他操作时有两种操作方法：他可以选择可以走到城市 $i+1$；或者如果 Kitten 不在城市 $i+2$，就可以绕过城市 $i+1$，暗渡走到 $i+2$。
- 假设 Kitten 在城市 $i$。轮到她操作时有两种操作方法：她可以选择可以走到城市 $i-1$；或者如果 33DAI 不在城市 $i-2$，就可以绕过城市 $i-1$，暗渡走到 $i-2$。
- 游戏最终的评分为“**33DAI 走到的所有城市的资源值之和**”减去“**Kitten 走到的所有城市的资源值之和**”的数值。
- 33DAI 的游戏目标为最大化最终评分，Kitten 的目标为最小化最终评分。
假设两个人都足够聪明，请你输出最终评分会是多少。
输入
第一行为一个数 $n$。
第二行为 $n$ 个整数 $a_1\sim a_n$。
第二行为 $n$ 个整数 $a_1\sim a_n$。
输出
一个整数，即最终评分。
样例输入 复制
2
1 3样例输出 复制
-2提示
游戏一开始就结束了。
```input2
4
2 2 2 2
```
```output2
2
```
显然如果第一轮 33DAI 往右走一步，Kitten 就也能往左走一步了，最终得分就是 $0$。所以 33DAI 第一轮就会暗渡到 $3$，会走过城市 $1,3$，Kitten 会走过城市 $4$。
```input3
4
2 6 2 2
```
```output3
4
```
- 比赛可能性 1：33DAI 走过城市 $1,3$，Kitten 会走过城市 $4$
- 比赛可能性 2：33DAI 走过城市 $1,2$，Kitten 会走过城市 $4,3$
显然 33DAI 会把游戏引导到第二种结果中。
## 数据规模与约定
对于 $100\%$ 的数据，$2 \le n \le 5\times 10^3$，$1\le a_i\le 10^9$。
- 子任务 1（10 分）：保证 $n=4$。
- 子任务 2（20 分）：保证 $a_i=33$。
- 子任务 3（30 分）：保证 $n=20$。
- 子任务 4（40 分）：没有特殊限制。
```input2
4
2 2 2 2
```
```output2
2
```
显然如果第一轮 33DAI 往右走一步，Kitten 就也能往左走一步了，最终得分就是 $0$。所以 33DAI 第一轮就会暗渡到 $3$，会走过城市 $1,3$，Kitten 会走过城市 $4$。
```input3
4
2 6 2 2
```
```output3
4
```
- 比赛可能性 1：33DAI 走过城市 $1,3$，Kitten 会走过城市 $4$
- 比赛可能性 2：33DAI 走过城市 $1,2$，Kitten 会走过城市 $4,3$
显然 33DAI 会把游戏引导到第二种结果中。
## 数据规模与约定
对于 $100\%$ 的数据，$2 \le n \le 5\times 10^3$，$1\le a_i\le 10^9$。
- 子任务 1（10 分）：保证 $n=4$。
- 子任务 2（20 分）：保证 $a_i=33$。
- 子任务 3（30 分）：保证 $n=20$。
- 子任务 4（40 分）：没有特殊限制。