100 #P1082. *【动态规划:状态设计DP】火车票

*【动态规划:状态设计DP】火车票

【题意】

nn 个站点(依次编号为 1n1 \sim n)。线路上的任意两个站点间的票价(CiC_i)和两站的距离(LL)关系如下:

0<LL10 < L \le L_1,票价为 C1C_1

L1<LL2L_1 < L \le L_2,票价为 C2C_2

L2<LL3L_2 < L \le L_3,票价为 C3C_3

任意两个相邻的车站的距离不超过 L3L_3

求从起点站到终点站的总车费的最小值。

【输入格式】

第一行6个整数 L1L_1L2L_2L3L_3C1C_1C2C_2C3C_31L1<L2<L31091 \le L_1 < L_2 < L_3 \le 10^91C1<C2<C31091 \le C_1 < C_2 < C_3 \le 10^9),中间用空格分隔。

第二行一个整数 nn2n1002 \le n \le 100),表示线路上的车站数。

第三行两个整数 xxyy,分别是起点站和终点站的编号。注意:xx 不一定小于 yy

以下的 n1n-1 个整数 a[i]a[i], a[i]a[i] 描述了第 ii 号站到 11 号站的距离。

任意两个车站的距离不超过 10910^9

【输出格式】

一个整数,表示从起点站到终点站的总车费的最小值。

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