提示: 欢迎访问OurACM平台。
Problem 1231 取数游戏问题

Accept: 158    Submit: 484
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

取数游戏是一个 2 人对策游戏。游戏开始时将 n 个数在棋盘上从左到右排成一行。甲乙双方轮流在这一行数的左右 2 端取数,直至全部取完 n 个数。每人所取得的数的总和为其得分值。最后双方得分多者获胜。游戏规定由甲方先取数。

★算法设计: 在甲乙双方都采用最优策略的前提下,计算甲方先取数时双方的最后得分。

Input

对于每组输入数据,输入数据的第 1 行有 1 个正整数 n (1<=n<=100),表示有 n 个数在棋盘上从左到右排成一行。接下来的 n 行中每行有 1 个整数,表示在棋盘上依次排列的 n 个数。

Output

输出计算出的双方的最后得分。甲方得分在前,乙方得分在后。

Sample Input

6 4 7 2 9 5 2

Sample Output

18 11

Source

FJ CFCS 2008

Submit  Back  Status  Discuss