1029 . A遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯，道歉！$

User's AC Ratio

89.8% (220/245)

Submission's AC Ratio

54.5% (310/569)

Tags

2007-CKcon CKcon DP

Description

「A遊戲」是個由兩個人玩的遊戲：有一串由 $N$ 個正整數所組成的數列，兩個玩者輪流拿走一個最左邊或最右邊的數，直到最後所有的數都取完之後，兩個玩者分別把自己所取到數加總，分數較高的人獲勝。
　　今假設兩個玩者都是最佳玩家──也就是說，兩者都不會犯錯，會就目前狀況盡自己的力取得盡量多的分數──試求兩個玩家所能得到的最高分數各為多少？

Input Format

首先是一個正整數 $N$，代表有幾個數（$1 \leq N \leq 1000$）。接下來有 $N$ 個正整數，代表遊戲開始時的這列數。

Output Format

兩個數字：第一位玩家（先拿者）的分數，以及第二位玩家的分數。

Sample Input 1

6
4 7 2 9 5 2

Sample Output 1

18 11

Hints

Problem Source

原TIOJ1029 / 96建中校內資訊能力競賽(prob6)
2021.03.01 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 600 262144 262144 1
1 600 262144 262144 2
2 600 262144 262144 3
3 600 262144 262144 4
4 600 262144 262144 5
5 600 262144 262144 6
6 600 262144 262144 7
7 600 262144 262144 8
Submit
Status
Ranklist
Back to Top