首页 > 代码库 > P1177 公路乘车 - Smart Online Judge
P1177 公路乘车 - Smart Online Judge
简单的动态规划
题目ID：1177
题目名称：公路乘车
有效耗时：15 ms
空间消耗：516 KB
程序代码：
1 #include<iostream> 2 using namespace std; 3 4 int f[11]; 5 int g[102]; 6 int main(){ 7 for(int i=1;i<=10;i++){ 8 cin>>f[i]; 9 }10 for(int i=1;i<=102;i++){11 g[i]=0;12 }13 14 int a;15 cin>>a;16 17 for(int i=1;i<=a;i++){18 int min=65536;19 if(i<=10){20 for(int j=1;j<=10;j++){21 if(i>=j&&(g[i-j]+f[j])<min)22 min=g[i-j]+f[j];23 }24 }25 else{26 for(int j=1;j<i;j++){27 if((g[i-j]+g[j])<min)28 min=g[i-j]+g[j];29 }30 }31 g[i]=min;32 // cout<<g[i]<<" ";33 }34 // cout<<endl;35 36 37 cout<<g[a]<<endl;38 // system("pause");39 return 0;40 41 }
题目描述
一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如样例的第一行就是一个费用的单子。
没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。
没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。
输入格式
第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。
第二行一个整数n表示，旅客的总路程数。
第二行一个整数n表示，旅客的总路程数。
输出格式
仅一个整数表示最少费用。
样例输入
12 21 31 40 49 58 69 79 90 10115
样例输出
147
数据范围与提示
P1177 公路乘车 - Smart Online Judge
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。