分数: 400 分
问题陈述
高桥和青木玩纸牌游戏。
N 卡片在桌子上排成一排,并且 i左起第张牌有一个整数 上面写着 V_i 。请注意 V_i 可能为负。
两名玩家按照以下规则取牌:
- 高桥第一,青木第二,他们轮流轮流。
- 在他们的回合中,玩家从其中选择一张牌 左端 或 右端 桌子上剩余的一排牌,拿起它,并将其放在他们的手上。拿走的牌从牌桌上移除,剩余牌的顺序不变。
- 当所有牌都被拿走后,游戏结束。
两名玩家都知道包括彼此策略在内的所有信息,并且各自都以最佳方式进行游戏,以最大化他们所拿的卡片上写的整数之和。
当双方都发挥最佳状态时,找出高桥拿走的牌上写着的整数之和减去青木拿走的牌上写着的整数之和所得到的值。
约束
- 1 \leq N \leq 3000
- -10^9 \leq V_i \leq 10^9
- 所有输入均为整数。
输入
N V_1 V_2 \ldots V_N
- 第一行包含一个整数 N 代表卡片数量。
- 第二行包含整数 每张卡片上写有 V_1, V_2, \ldots, V_N ,并用空格分隔。在这里, V_i 是写在 i左起第一张牌。
输出
当两名玩家都发挥最佳状态时,用一行打印出高桥拿走的牌上写着的整数之和减去青木拿走的牌上写着的整数之和所得到的值。
示例输入 1
4 3 1 2 5
示例输出 1
3
示例输入 2
4 -1 5 -3 2
示例输出 2
11
示例输入 3
10 8 -3 5 12 -7 2 9 -1 6 4
示例输出 3
15
示例输入 4
20 15 -8 23 4 -12 7 19 -3 11 6 -5 14 2 -9 18 1 -6 10 8 -2
示例输出 4
53
示例输入 5
1 -1000000000
示例输出 5
-1000000000