把整段路抽象为:行驶段 c1,…,cn 与中间等待段 t1,…,tn−1。 一次连续乘坐时长为 L 的费用函数为

关键:等待段可以选择“在车上”(把相邻行驶段合并成一个更长的连续乘坐)或“下车”(不计费并切断一次乘坐)。因此问题变成:在每个等待点处,决定“合并”还是“断开”,使 ∑f(每次连续乘坐长度) 最小。
小明去了另一个城市旅游。他打算坐出租车到下一个景点。
众所周知,出租车有起步价和单价。但是这个城市的出租车却有些特殊,是以分钟为单位计价。
在某一个给定的时间内,只需要付起步价;用时超过该时间后,每分钟需额外付单价。
具体的,设起步价为 a 元,单价为 b 元,给定的时间为 s 分钟,则总价钱 y 与分钟数 x 可以用以下的函数关系式表示:
$\mathrm{y}=\left\{\begin{array}{c}a, x \leq s \\a+b \cdot(x-s), x>s\end{array}\right. $
不幸的是,小明当前的位置与目的地之间有很多的红绿灯,因此出租车行驶一会儿就必须停下来等红绿灯。
现在小明算出了每段路出租车会行驶的时间以及停留的时间。
假设小明可以随时随地下出租车,并且一下出租车就能立马打到另一辆出租车。
请帮助小明规划打车的方案,使他所需付的钱最少。
第一行三个整数 a,b,s(1≤a,b,s≤105,a>b•s) ,表示出租车的起步价,单价,以及起步价对应的分钟数。
第二行一个整数 n(2≤n≤106) ,表示从小明所处的位置到景点共有 n 段路。
第三行 n 个整数,其中第 i 个整数 ci(s≤ci≤105) 表示第 i 段路的用时,单位为分钟。
第四行 n−1 个整数,其中第 i 个整数 t(1≤t≤105) 表示第 i 段路与第 i+1 段路之间需要等待的时间,单位为分钟。
一行,一个整数,表示所需付的钱的最小值。
输入
7 1 5
4
6 7 5 8
1 11 1
输出
32
说明
一种可行的方案为:在第一段路打车,第二段路结束时下车;在第三段路重新打车,一直坐到目的地。总花费为 [7+1∗(6+1+7−5)]+[7+1∗(5+1+8−5)]=32 元,可以证明此为最小花费。