宝箱(usaco)

宝箱(usaco)

测试数据来自 wjszez/2174

【描述】
Bessie和Bonnie发现了一个装满了非凡的金币的宝箱! 作为奶牛,尽管, 他们无法走进一家商店购买物品,因此他们决定开心的玩一玩这些金币。
N (1 <= N <= 5,000)个金币放置在一条直线上,每个金币的价值为C_i (1 <= C_i<= 5,000)。Bessie和Bonnie轮流操作,每一轮中,她从直线的左端或者右端取走一枚金币。金币全部取完时游戏结束。
Bessie和Bonnie都想要让自己尽可能得到更多的财富。Bessie先开始游戏。请帮忙她算出她能获得的最大价值。假设两个奶牛都以最优的方法进行游戏。
考虑一局游戏,四个金币排成一行,价值如下所示:
            30  25  10  35

考虑如下的游戏过程:               
玩家     端点    金币价值       总分     总分        排列状态
Bessie    右         35            35         0        30  25  10
Bonnie    左         30            35        30         25  10
Bessie    左         25            60        30            10
Bonnie   右         10            60         40           --

这是Bessie能做到的最优游戏方式。
PROBLEM NAME: treasure
输入格式:
* 行1:一个数N
* 行2..N+1:行i+1为一个整数C_i

样例输入 (treasure.in):
4
30
25
10
35

输出格式:
* 行1: 一个整数,即Bessie能赢得的最大价值。
样例输出 (treasure.out):
60

信息

ID
2582
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者