408567: GYM103186 J Alice and Bob-1
Description
众所周知,Alice 和 Bob 是很好的朋友,他们总是喜欢在一起玩有趣的游戏。并且他们每个人都很争强好胜并且高智商,都想尽力赢下对方。但由于 Alice 是女生,Bob 很有绅士风度,总是会让 Alice 先手。
今天他们遇到的游戏是这样的,给定 $$$ n $$$ 张卡片,每张卡片都有一个数值。他们每个人轮流交替取走一张卡片,直到取完。
定义手中卡片的价值是所有你取得的卡片数值的和的绝对值,即假设 Alice 取走的卡为$$$\pi_1,\dots, \pi_k$$$,那么她所拥有的价值为 $$$A=\left |\sum\limits_{j=1}^k a_{\pi_j}\right |$$$,Bob 所拥有的价值为 $$$B=\left |\sum\limits_{i=1}^n a_i - \sum\limits_{j=1}^k a_{\pi_j}\right |$$$。
Alice 想让她取得的卡片的价值相比于 Bob 所取得的尽可能大,而 Bob 不想被 Alice 拉开差距,即 Alice 希望最终 $$$A-B$$$ 的值尽可能地大,而 Bob 希望这个值尽可能地小。
他们都想知道,在他们都采取最优策略的情况下,最终 Alice 所取得的卡片价值和 Bob 所取得的卡片价值的差会是多少?
Input第一行有一个整数 $$$ n $$$ ($$$ 1 \leq n \leq 5000 $$$),表示卡片的数量。
第二行有 $$$ n $$$ 个整数 $$$a_1, a_2,\cdots,a_n$$$($$$-10^9 \leq a_i \leq 10^9$$$),中间以空格分隔,分别表示第 $$$i$$$ 张卡片上的数值为 $$$a_i$$$ 。
Output在一行输出一个整数,代表最终 Alice 所取得的卡片价值和 Bob 所取得的卡片价值的差。
ExamplesInput1 100Output
100Input
3 4 5 1Output
2Input
6 1 2 3 4 5 6Output
3