795 . YP 與水果軟糖
TopCoder
Description
小 Y 和小 P 獲得了一罐水果軟糖，水果軟糖罐頭尾都有開口，裡面一共有 $N$ 個軟糖，每一顆軟糖都有屬於它的「好吃度」，小 Y 和小 P 都已經知道這 $N$ 顆軟糖的好吃度了。小 Y 和小 P 想要平分這罐水果軟糖，為了公平起見，他們決定輪流從罐子裡取出一顆軟糖，軟糖只能從頭或尾拿出，直到全部被拿完為止，由小 Y 先拿。假設最後小 Y 拿到的水果軟糖好吃度總和為 $Y$，小 P 拿到的水果軟糖好吃度總和為 $P$，雙方都想要最大化自己和對方的差距，也就是說小 Y 想要最大化 $Y - P$，小 P 則想要最小化 $Y - P$，請問在雙方的最佳策略下，$Y - P$ 的值為多少？
Input Format
輸入第一行有一個正整數 $N (1 \leq N \leq 3000)$，代表水果軟糖的數量。
輸入第二行包含 $N$ 個正整數 $a_1, a_2, \ldots, a_N (1 \leq a_i \leq 10^ 9)$，分別代表 $N$ 顆水果軟糖的好吃度。
Output Format
請輸出一個整數代表在雙方最佳策略下 $Y - P$ 的值。
Sample Input 1
3
2 5 6
2 5 6
Sample Output 1
3
Sample Input 2
6
7 8 1 6 3 6
7 8 1 6 3 6
Sample Output 2
9
Hints
Problem Source
AtCoder
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~18 | 無額外限制 | 100 |