1029 . A遊戲
TopCoder
Tags
Description
「A遊戲」是個由兩個人玩的遊戲：有一串由N個正整數所組成的數列，兩個玩者輪流拿走一個最左邊或最右邊的數，直到最後所有的數都取完之後，兩個玩者分別把自己所取到數加總，分數較高的人獲勝。
今假設兩個玩者都是最佳玩家──也就是說，兩者都不會犯錯，會就目前狀況盡自己的力取得盡量多的分數──試求兩個玩家所能得到的最高分數各為多少？
Input Format
首先是一個正整數n，代表有幾個數（1<=n<=1,000）。接下來有n個正整數，代表遊戲開始時的這列數。
Output Format
兩個數字：第一位玩家（先拿者）的分數，以及第二位玩家的分數。
Sample Input
6
4 7 2 9 5 2
4 7 2 9 5 2
Sample Output
18 11
Hints
Problem Source
原TIOJ1029 / 96建中校內資訊能力競賽(prob6)
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 (KiB) | Output Limit (KiB) | Subtasks |
|---|---|---|---|---|
| 0 | 600 | 262144 | 262144 | |
| 1 | 600 | 262144 | 262144 | |
| 2 | 600 | 262144 | 262144 | |
| 3 | 600 | 262144 | 262144 | |
| 4 | 600 | 262144 | 262144 | |
| 5 | 600 | 262144 | 262144 | |
| 6 | 600 | 262144 | 262144 | |
| 7 | 600 | 262144 | 262144 |