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
For Testdata: 0 ~ 0, Score: 12
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 12
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 12
For Testdata: 5 ~ 5, Score: 12
For Testdata: 6 ~ 6, Score: 12
For Testdata: 7 ~ 7, Score: 16
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 12
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 12
For Testdata: 5 ~ 5, Score: 12
For Testdata: 6 ~ 6, Score: 12
For Testdata: 7 ~ 7, Score: 16
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) |
|---|---|---|---|
| 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 |