Dotcpp  >  编程题库  >  硬币游戏
题目 1342:

硬币游戏

时间限制: 1s 内存限制: 128MB 提交: 27 解决: 12

题目描述

最初地面上有一堆n个硬币(5< =n< =2000),从上面数第i个硬币的价值为C_i(1< =C_i< =100000); 游戏开始后,A先取一枚或两枚硬币。如果A取了一枚,那么B可以继续取一枚或两枚;如果A取了两枚,那么B可以取一到四枚硬币。每次都只能从最上面取。每一次,当前取硬币的人都至少取一枚硬币,最多可以取他的对手上一次取硬币数目的两倍。当没有硬币可取的时候,游戏就结束了。 然后,他们就可以用得到的硬币向John买东西,当然,他们游戏的目的就是要尽可能使自己得到的硬币价值更大。现在你的任务是,求出在两个人都想得到更大价值的情况下,游戏结束后,第一个人最多能得到的硬币价值。

输入格式

第1行:  一个整数,N(5< =N< =2000)。  第2到n+1行:  第  i+1  行代表从上数第i枚硬币的价值。

输出格式

一行:一个数字,第一个人能得到的最大价值

样例输入

5
1
3
1
7
2

样例输出

9

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签