有一天,home_w和seventh在玩石子游戏,规则是这样的:有n堆石子,每堆石子个数为ai。他们从第1堆开始按顺序选择到第n堆,seventh先手,当轮到某个人时,有两种操作:
若这个人选择将这堆石子归入囊中,那么下一轮主动权交给对方
这个人可以将这堆石子给对方,那么下一轮主动权还是归自己
他们两人都很聪明,都采取最优策略让自己能得到的石子尽可能多,请问他们最后分别能得到多少个石子。
第一行输入一个t,表示有t组数据。
接下来t组数据,先输入一个n,表示有n堆石子,然后n个正整数ai,表示第 i 堆石子的个数。
保证n的和不超过100000,1<=ai<=100000,保证每组数据的石子总数在int范围内。
输出 t 行,每行两个数,分别表示home_w和seventh的最后得分。
1 5 10 21 10 21 10
31 41 Hint: 第一轮:seventh选择将第一堆给home_w,下一轮还是由seventh选择,此时 10:0 第二轮:seventh选择拿走第二堆,下一轮变为由home_w选择,此时 10:21 第三轮:home_w选择将第三堆给seventh,下一轮还是由自己选择,此时 10:31 第四轮:home_w选择拿走第四堆,下一轮变为seventh选择,此时 31:31 第五轮:seventh拿走第五堆,游戏结束 31:41