797 . B-Game

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Josh
\begin{flalign} \LARGE\text{.} \end{flalign}

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

20.0% (3/15)

Tags

apcsc apcsc-dp

Description

你聽過 H-Game 嗎？想必你一定是箇中高手。

但目前時下最流行的遊戲並不是 H-Game，而是 B-Game。小 A 和小 C 打算利用這款 B-Game 進行一場史詩級的大對決，B-Game 是一款殘酷的卡牌對戰遊戲，檯面有 $N$ 張怪獸卡，排成一個環狀，每張怪獸卡都有相應的戰鬥力。接著兩個人輪流從檯面上取走一張怪獸卡，由小 A 先選擇，為了公平起見，除了第一次選怪獸卡以外，每一次選卡都只能選擇上一位玩家選擇的怪獸卡左邊或右邊。舉例來說，如果場上有五張卡 $1, 2, 3, 4, 5$ 排成環狀，小 A 拿了編號 $3$，小 C 拿了編號 $2$ 以後，小 A 就可以選取編號 $1$ 或 $4$ 的卡片。

由選完怪獸卡後，兩個人會同時發動攻擊，遊戲的勝負就取決於雙方怪獸卡的攻擊力總和，總和較高的人就會取得勝利，小 A 希望他能夠贏得這個遊戲的勝利，而不至於落敗成為 B 咖，請你幫小 A 計算他一開始有幾種選卡方式（即第一張卡片）可以幫助他獲得最後的勝利，除此之外，他還想知道在最佳的策略下，他的怪獸們攻擊力總和最高可以達到多少。

Input Format

輸入第一行包含一個正整數 $N (1 \leq N \leq 5000)$，代表檯面上的怪獸卡數量。
輸入第二行包含 $N$ 個正整數 $w_1, w_2, \ldots, w_N$，分別代表每一張怪獸的攻擊力，並且它們已按照順時針的順序排在檯面上，輸入保證這些卡片的攻擊力總和不超過 int 型態範圍。

Output Format

請在一行中輸出兩個整數並用一個空白分開，第一個整數代表小 A 一開始有幾種選取卡片的方法可以幫助他在最後獲得勝利，第二個整數代表小 A 最多可以拿到的怪獸攻擊力總和。

Sample Input 1

6
4 7 2 9 5 2

Sample Output 1

4 18

Sample Input 2

5
8 7 4 8 3

Sample Output 2

1 18

Hints

Problem Source

TIOJ

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~21 無額外限制 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
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
Submit
Back to Top