UOJ Logo FLYIOI UOJ

FLYIOI

#4. 取数游戏2

问题描述

考虑一个由两个玩家玩的游戏。游戏开始前给定一串排成一排的N个数字。两位玩家轮流从这一串数中的最左端或者最右端取出一个数。当所有数字都被取完后,游戏结束。此时,两位玩家各自的得分将是他所有取出的数的和。得分较高的玩家获胜。假设你是先取者。请编写程序制定一个游戏的最佳策略。最佳策略是指这样一种数字取法,它能在最坏的情况(后取者的策略对自己最不利的情况)下得到最高的得分。

输入格式

数据的第一行是一个正整数N,输入数据保证1<=N<=100。第二行从左至右给出了游戏初始时的N个正整数。这些正整数保证不超过200。

输出格式

输出两个用空格隔开的正整数。他们分别表示游戏的先取者在最坏情况下最高的得分和此时后取者的得分。

样例输入

6
4 7 2 9 5 2

样例输出

18 11

时间限制

各测试点1秒

内存限制

你的程序将被分配128MB的运行空间

提交

UPC