1. 首页
  2. 代码宅, 动态规划(DP)

【火车票】

题目描述

从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近似的表示为一条线段,火车站就是线段上的点。线路始于Ekaterinburg,终于Sverdlovsk。Ekaterinburg被标号为1,Sverdlovsk被标号为n。(n为整条线路上的站点数)

线路上的任意两个站点间的直达票价是由它们间的距离决定的,票价根据以下规则制定:

如果两站的间距超过L3,则无直达车票。所以有时可能有必要买多张票,通过转车的方式,从一个站到达另一个站。
例如,在上面的图中,有7个站点。2号站点到6号站点的距离超过L3,不能买直达票。存在若干种中转的方法,其中的一种是买两张票:先花费C2从2号站到达3号站,然后花费C3从3号站到6号站,一种花费C2+C3。

你的任务是,找出一种最经济的中转方案。

 

输入格式

第一行 6 个整数L1, L2, L3, C1, C2, C3(1<=L1<L2<L3<=109, 1<=C1<C2<C3<=109),中间用空格分隔。
第二行一个整数 n(2<=n<=100),表示线路上的车站数。
第三行两个整数 s 和 t,分别是起点和终点的编号。注意:s 不一定小于 t。
以下的 n-1 行,按据Ekaterinburg远近,每行描述了一个车站的位置。它包含一个整数,表示该车站距Ekaterinburg的距离。
任意两个车站的距离不超过109,任意两个相邻的车站的距离不超过L3。

输出格式

一个整数,表示从给定的一个站到给定的另一个站的最小花费。

样例数据 1

输入

3 6 8 20 30 40
7
2 6
3
7
8
13
15
23

输出

70

DP水题一发,直接把每个点枚举一遍计算能不能更新就行了……
评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

发表评论

gravatar

*

沙发空缺中,还不快抢~