795 . YP 與水果軟糖

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

66.7% (4/6)

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≤N≤3000)，代表水果軟糖的數量。
輸入第二行包含 N 個正整數 a1,a2,…,aN(1≤ai≤109)，分別代表 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