2102: 【动态规划】【背包】最小乘车费用

本文主要是介绍2102: 【动态规划】【背包】最小乘车费用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

某条街上每一公里就有一汽车站，乘车费用如下表：

公里数	1	2	3	4	5	6	7	8	9	10
费用	12	21	31	40	49	58	69	79	90	101

而一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的，且汽车不能往回坐）。

编一程序：

      从文件中读入对乘车费用的描述；算出最小的价格；

输入

输入文件共两行，第一行为10个不超过101的整数，依次表示行驶1～10公里的费用，相邻两数间用空格隔开；第二行为某人想要行驶的公里数。

输出

输出文件仅一行包含一个整数，表示该测试点的最小费用。

样例输入

12 21 31 40 49 58 69 79 90 101
15

样例输出

147

Code:

#include<bits/stdc++.h>
using namespace std;
int main(){int s,c[15],f[10005];for(int i=1;i<=1005;i++){f[i]=INT_MAX;}f[0]=0;for(int i=1;i<=10;i++){cin>>c[i];}cin>>s;for(int i=1;i<=10;i++){for(int v=i;v<=s;v++){f[v]=min(f[v],f[v-i]+c[i]);}}cout<<f[s];return 0;
}

 

这篇关于2102: 【动态规划】【背包】最小乘车费用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---