795 . YP 與水果軟糖

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

60.0% (3/5)

Tags

apcsc apcsc-dp

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

Sample Output 1

3

Sample Input 2

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
Submit
Back to Top