问题 B: 跑步
传统题
1.000s
时间限制
256MB
内存限制
10 提交
10 解决
【题目描述】
题目描述
小爱在参加一个跑步比赛，比赛路线分为 n
段，其中第 i 段的分数为 ai
。在每段路上，小爱可以选择正常跑步、冲刺或慢走，每种方式得分不同，具体规则如下：
如果在一段路上选择跑步，可以得 ai
分；
如果在一段路上选择冲刺，分数会加倍，变成 2*ai
分，但下一段路就只能慢走了；
如果在一段路慢走，得分为 0。
小爱在每段路上应该如何选择，才能使得分之和最大呢？
输入格式
第一行：单个正整数 n。
第二行：n 个正整数表示 a1
到 an
。
输出格式
单个整数：表示答案。
数据范围
对于 30% 的数据，1≤n≤100
；
对于 60% 的数据，1≤n≤1000
；
对于 100% 的数据，1≤n≤100000
；
1≤ai≤10000
。
样例数据
输入:
4
1 2 3 4
输出:
14
说明:
前几段都正常跑步，最后一段冲刺，得分为1+2+3+4*2