← 返回题单

题单练习背包DP

← 上一题下一题 →

A70759 | $公交乘车$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

A城市有一条非常特别的街道，该街道在每个公里的节点上都有一个公交车站，乘客可以在任意的公交站点上车，在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费，比如，下表就是乘客乘坐不同的公里数要付的费用。（请注意：不一定公里数越高，费用越高，这也是这条街道特别的地方） 公里数 1 2 3 4 5 6 7 8 9 10 付费金额 12 21 31 40 49 58 69 79 90 101 一辆公交车单次行驶的公里数一定不超过 10 公里，一个乘客如果打算乘坐公交车完成 n 公里（1 \le n \le 100）的行程，他可以选择无限次的换车来完成行程。 请问，他最少要花多少钱？

输入格式

第一行十个整数分别表示公交行走 1 到 10 公里的费用（ \le 500）。注意这些数并无实际的经济意义，即行驶 10 公里费用可能比行驶一公里少。 第二行一个整数 n 表示，旅客的总路程数。（1 \le n \le 100）

输出格式

仅一个整数表示最少费用。

输入输出样例

输入 #1

12 21 31 40 49 58 69 79 90 101
15

输出 #1

C++ 编辑器

输入

输出