#PQJ325x6154. QOJ 325_6154

    ID: 2916 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:AHOI 2014

QOJ 325_6154

2014 年安徽省青少年信息学奥林匹克竞赛 中学组试题 安徽 合肥 2014.4.19 保龄球 【故事背景】 JYY 很喜欢打保龄球,虽然技术不高,但是还是总想着的高分。这里JYY 将向你介绍他所参加的特殊保龄球比赛的规则,然后请你帮他得到尽量多的分数。 【问题描述】 一场保龄球比赛一共有N 个轮次,每一轮都会有10 个木瓶放置在木板道的 另一端。每一轮中,选手都有两次投球的机会来尝试击倒全部的10 个木瓶。对 于每一次投球机会,选手投球的得分等于这一次投球所击倒的木瓶数量。选手每 一轮的得分是他两次机会击倒全部木瓶的数量。 对于每一个轮次,有如下三种情况: 1、“全中”:如果选手第一次尝试就击倒了全部10 个木瓶,那么这一轮就称 为“全中”。在一个“全中”轮中,由于所有木瓶在第一次尝试中都已经被击倒, 所以选手不需要再进行第二次投球尝试。同时,在计算总分时,选手在下一轮的 得分将会被乘2 计入总分。 2、 “补中”:如果选手使用两次尝试击倒了10 个木瓶,那么这一轮就称为“补 中”。同时,在计算总分时,选手在下一轮中的第一次尝试的得分将会被乘以2 计入总分。 3、“失误”:如果选手未能通过两次尝试击倒全部的木瓶,那么这一轮就被 称为“失误”。同时,在计算总分时,选手在下一轮的得分会被计入总分,没有 分数被翻倍。 此外,如果第N 轮是“全中”,那么选手可以进行一次附加轮:也就是,如 果第N 轮是“全中”,那么选手将一共进行N+1 轮比赛。显然,在这种情况下, 第N+1 轮的分数一定会被加倍。 附加轮的规则只执行一次。也就是说,即使第N+1 轮选手又打出了“全中”, 也不会进行第N+2 轮比赛。因而,附加轮的成绩不会使得其他轮的分数翻番。 最后,选手的总得分就是附加轮规则执行过,并且分数按上述规则加倍后的 每一轮分数之和。 JYY 刚刚进行了一场N 个轮次的保龄球比赛,但是,JYY 非常不满意他的 得分。 JYY 想出了一个办法:他可以把记分表上,他所打出的所有轮次的顺序重新 排列,这样重新排列之后,由于翻倍规则的存在,JYY 就可以得到更高的分数了! 当然了,JYY 不希望做的太假,他希望保证重新排列之后,所需要进行的轮 数和重排前所进行的轮数是一致的:比如如果重排前JYY 在第N 轮打出了“全 中”,那么重排之后,第N 轮还得是“全中”以保证比赛一共进行N+1 轮;同样 的,如果JYY 第N 轮没有打出“全中”,那么重排过后第N 轮也不能是全中。 请你帮助JYY 计算一下,他可以得到的最高的分数。

2014 年安徽省青少年信息学奥林匹克竞赛 中学组试题 安徽 合肥 2014.4.19 【输入格式】 从文件bowling.in 中读入数据。 第一行包含一个整数N,表示保龄球比赛所需要进行的轮数。 接下来包含N 或者N+1 行,第i 行包含两个非负整数 和 ,表示JYY 在 这一轮两次投球尝试所得到的分数, 表示第一次尝试, 表示第二次尝试。 我们用 表示一个“全中”轮。输入数据保证 。 读入数据存在N+1 行,当且仅当 且 。 【输出格式】 输出到文件bowling.out 中。 输出一行一个整数,表示JYY 最大可能得到的分数。 【样例输入】 2 5 2 10 0 3 7 【样例输出】 44 【样例说明】 按照输入顺序,JYY 将得到37 分。 最佳方案是将3 个轮次排列成如下顺序: 3 7 10 0 5 2 【数据规模与约定】 对于20%的数据满足 ; 对于50%的数据满足 ; 对于100%的数据满足 。