1349 板猪的火车票
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
奸商zn（请勿对号入座）开办了一家火车公司，弱弱的板猪要去看望她的朋友小板猪，万恶的zn对板猪实施各种提高价，板猪不寒而栗。。。
铁路线上有n(2<=n<=10000)个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示：
站之间的距离 - X 票价
0<X<=L1 C1
L1<X<=L2 C2
L2<X<=L3 C3
其中L1，L2，L3，C1，C2，C3都是已知的正整数，且(1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9)。显然若两站之间的距离大于L3，那么从一站到另一站至少要买两张票。注意：每一张票在使用时只能从一站开始到另一站结束。
现在板猪要从A到B，为了不让奸商zn敲竹杠，你能帮助板猪吗？
输入描述 Input Description
输入文件的第一行为6个整数, L1, L2, L3, C1, C2, C3 (1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9) ,这些整数由空格隔开.第二行为火车站的数量N (2 <= N <= 10000).第三行为两个不同的整数A、B,由空格隔开。接下来的 N-1 行包含从第一站到其他站之间的距离.这些距离按照增长的顺序被设置为不同的正整数。相邻两站之间的距离不超过L3. 两个给定火车站之间行程花费的最小值不超过10^9，而且任意两站之间距离不超过 10^9。
输出描述 Output Description
输出文件中只有一个数字,表示从A到B要花费的最小值.
样例输入 Sample Input
3 6 8 20 30 40
7
2 6
3
7
8
13
15
23
样例输出 Sample Output
70
/*基本思路：序列性DP
f[i]数组储存着从A到i的最小花费，它是由它之前的站点中可以用一张票坐过来的，以此更新*/
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 10001
int l[],c[],n,A,B;
long long int sum[N],f[N];
void input()
{
for(int i=;i<=;++i)
scanf("%d",&l[i]);
for(int i=;i<=;++i)
scanf("%d",&c[i]);
scanf("%d",&n);
sum[]=;
scanf("%d%d",&A,&B);
for(int i=;i<=n;++i)
scanf("%d",&sum[i]);
}
int judge(int a,int b)
{
int cha=a-b;
if(a-b<=l[]) return ;/*让从t--i选取价格尽量低的票*/
if(a-b<=l[]) return ;/*一二三是判断买那张票*/
if(a-b<=l[]) return ;
return ;
}
void DP()
{
memset(f,,sizeof(f));
f[A]=;
int flag=;
for(int i=A+;i<=B;++i)
for(int t=A;t<=i-;++t)
{
flag=judge(sum[i],sum[t]);/*判读买那张票*/
if(!flag) continue;/*不能一次到达*/
f[i]=min(f[i],f[t]+c[flag]);/*否则的话更新f[i]的最小数*/
}
}
int main()
{
input();
DP();
cout<<f[B];
return ;
}