bzoj#P2017. [USACO2009 Nov] 硬币游戏

[USACO2009 Nov] 硬币游戏

题目描述

农夫约翰的奶牛喜欢玩硬币游戏,因此他发明了一种称为「Xoinc」的两人硬币游戏。初始时,一个有 nn 枚硬币的堆栈放在地上,从堆顶数起的第 ii 枚硬币的币值为 cic_i。开始玩游戏时,第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币,那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币,则第二个玩家可以拿走 11223344 枚硬币。在每一轮中,当前的玩家至少拿走一枚硬币,至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时,游戏结束。两个玩家都希望拿到最多钱数的硬币。请问,当游戏结束时,第一个玩家最多能拿多少钱呢?

输入格式

第一行:11 个整数 nn

第二行到第 n+1n+1 行:第 i+1i+1 行包含 11 个整数 cic_i

输出格式

11 个整数表示第一个玩家能拿走的最大钱数。

5
1
3
1
7
2
9

样例说明 1

第一个玩家先取走第一枚,第二个玩家取第二枚;第一个玩家取走第三、四两枚,第二个玩家取走最后一枚。

数据规模与约定

对于 100%100\% 的数据,5n2×1035 \leq n \leq 2\times10^31ci1051 \leq c_i \leq 10^5

题目来源

Silver