【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 104233
  • 排名 - 233

最新评论

阅读排行榜

评论排行榜

 【问题描述】

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。

kilometres

1

2

3

4

5

6

7

8

9

10

price

12

21

31

40

49

58

69

79

90

101

没有一辆车子行驶超过10公里,一个顾客打算行驶n公里(1<=n<=100),它可以通过无限次的换车来完成旅程。最后要求费用最少。

 

【输入文件】

第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义,即行驶10公里费用可能比行驶一公里少。

第二行一个整数n表示,旅客的总路程数。

 

【输出文件】

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

 

【输入输出样例】

输入:

12 21 31 40 49 58 69 79 90 101

15

 

输出:

147

分析:简单的《无限背包》就是由10公里不断的去填顾客的n公里找最少的乘车费。

【参考程序】:

#include<string.h>
#include
<stdio.h>
#include
<stdlib.h>
long a[11],f[101];
long n;
int main()
{
        freopen(
"busses.in","r",stdin);
        freopen(
"busses.out","w",stdout);
        
for (int i=1;i<=10;i++) scanf("%ld",&a[i]);
        scanf(
"%ld",&n);
        
for (int i=1;i<=n;i++) f[i]=0xfffffff;
        f[
0]=0;
        
for (int i=1;i<=10;i++)
                
for (int j=1;j<=n;j++)
                        
if (f[j-i]+a[i]<f[j])
                                f[j]
=f[j-i]+a[i];
        printf(
"%ld\n",f[n]);
        
return 0;
}
posted on 2009-04-13 10:24 开拓者 阅读(541) 评论(1)  编辑 收藏 引用 所属分类: 动态规划&背包

Feedback

# re: 【公路乘车(Busses)】[未登录] 2010-08-08 16:40 wang
for (int j=1;j<=n;j++),此句是否应为 for (int j=i;j<=n;j++)
否则f[j-i]溢出了  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理