304504: CF859C. Pie Rules

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Pie Rules

题意翻译

## Description 有一个长度为$n$的序列,Alice和Bob在玩游戏。Bob先手掌握决策权。 他们从左向右扫整个序列,在任意时刻,拥有决策权的人有如下两个选择: >将当前的数加到自己的得分中,并将决策权给对方,对方将获得下一个数的决策权 >将当前的数加到对方的得分中,并将决策权保留给自己,自己将获得下一个数的决策权 假定他们都使用最优策略,求他们最后分别能获得多少分 ## Input 第一行是一个整数$n$代表序列长度 第二行有$n$个用空格隔开的整数,代表这个序列 ## Output 输出一行两个用空格隔开的整数,代表Alice和Bob的最终得分 ## Hint $Forall:$ $0~\leq~n~\leq~50$。 若设序列为$a$,则$1~\leq~a_i~\leq~100000$ 感谢@一扶苏一 提供的翻译

题目描述

You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person. The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left. All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?

输入输出格式

输入格式


Input will begin with an integer $ N $ ( $ 1<=N<=50 $ ), the number of slices of pie. Following this is a line with $ N $ integers indicating the sizes of the slices (each between $ 1 $ and $ 100000 $ , inclusive), in the order in which they must be handed out.

输出格式


Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.

输入输出样例

输入样例 #1

3
141 592 653

输出样例 #1

653 733

输入样例 #2

5
10 21 10 21 10

输出样例 #2

31 41

说明

In the first example, Bob takes the size $ 141 $ slice for himself and gives the decider token to Alice. Then Alice gives the size $ 592 $ slice to Bob and keeps the decider token for herself, so that she can then give the size $ 653 $ slice to herself.

Input

题意翻译

## Description 有一个长度为$n$的序列,Alice和Bob在玩游戏。Bob先手掌握决策权。 他们从左向右扫整个序列,在任意时刻,拥有决策权的人有如下两个选择: >将当前的数加到自己的得分中,并将决策权给对方,对方将获得下一个数的决策权 >将当前的数加到对方的得分中,并将决策权保留给自己,自己将获得下一个数的决策权 假定他们都使用最优策略,求他们最后分别能获得多少分 ## Input 第一行是一个整数$n$代表序列长度 第二行有$n$个用空格隔开的整数,代表这个序列 ## Output 输出一行两个用空格隔开的整数,代表Alice和Bob的最终得分 ## Hint $Forall:$ $0~\leq~n~\leq~50$。 若设序列为$a$,则$1~\leq~a_i~\leq~100000$ 感谢@一扶苏一 提供的翻译

加入题单

上一题 下一题 算法标签: