问题 2936 --自行车比赛【bike】

2936: 自行车比赛【bike】

题目描述

  卡卡西拿出电脑,列出了条件,很快找到了规律,“第二关,搞定”,铁人老 师不敢相信的看着电脑上的计算数字,狠狠的拍了卡卡西的肩膀,“嘿,你可帮 了大忙了,得好好谢谢你啊!”。“哈哈,不客气,请我吃个冰棍就行啦!”,卡卡 西笑着对老师说,“要不咱们一鼓作气,攻克最后一个难题?”表情明显轻松下 来的铁人老师充满希望的望着卡卡西,“恩,好的,争取快点解决,下午我也可 以早点回家啦”,卡卡西答应了老师。

自行车比赛的赛制本次有所创新,使用共享单车,且每隔一公里都有一个换 乘点,每次换车最多骑行 10 公里,假设按骑行公里数收费,且连续骑行 1 到 10 公里费用不等。一个小朋友要骑行 n 公里,那么怎样换乘共享单车,能使得骑行 n 公里总费用最少呢?

“这个好像有点复杂,不过难不倒我”卡卡西心中给自己加了把劲 ,仔细 计算起来,铁人老师核对了一下,确实没问题,激动地把卡卡西举了起来, “果然解决了,现在所有问题都没了,走,老师给你买雪糕去!”

五一当天,彩旗飞扬,“迷你铁人三项赛”如期举行,有了卡卡西的帮助, 一切都很顺利,卡卡西也满足了自己现场观看比赛的愿望,组委会也给她颁发 了一枚“优秀志愿者”的奖章,卡卡西把它佩戴在胸前,到现在还在闪闪发光 呢。

输入

输入数据共两行。

第一行为一个正整数 n,表示小朋友要骑行的总路程数。

第二行共十个正整数(中间空格隔开),第 i 个正整数表示 连续骑行 i 公 里的费用 Wi。注意这些数并无实际的经济意义,即骑行 10 公里费用可能 比骑行 1 公里的少。

输出

仅一个正整数,表示最少的费用

样例输入输出

输入#1 复制
18
3 5 9 10 6 20 18 10 30 40
输出#1 复制
22

提示

【样例说明】
输入数据第一行 18,表示小朋友要骑行的总路程为 18 公里,输入数 据第二行 10 个数,分别表示连续骑行 1 公里的费用为 3,连续骑行 2 公里的费用为 5,连续骑行 3 公里的费用为 9...以此类推,连续骑行 10 公里的费用为 40。为了骑行总费用最少,可采用的换乘方案是: 先骑行 8 公里,花费为 10;换乘后再骑行 5 公里,花费为 6;换乘后 再骑行 5 公里,花费为 6;总路程为 8+5+5=18 公里,总费用为 10+6+6=22。

【数据范围】
100%的数据:0<Wi<=500,1<=n<=100。

序号 标题 作者 发表时间 费用 订购数 操作