记录编号	194402	评测结果	AAAAAAAAAAAAAAAA
题目名称	[Ural 1031] 火车票	最终得分	100
用户昵称	旧梦	是否通过	通过
代码语言	C++	运行时间	0.840 s
提交时间	2015-10-16 16:36:59	内存使用	0.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cstring>
#define LL long long
using namespace std;
const int maxn=10000+10;
int L1,L2,L3,C1,C2,C3,n,st,en;
LL dp[maxn],dis[maxn];

int main(){
	freopen("rail.in","r",stdin);
	freopen("rail.out","w",stdout);
	scanf("%d%d%d%d%d%d",&L1,&L2,&L3,&C1,&C2,&C3);
	scanf("%d%d%d",&n,&st,&en);
	for (int i=2;i<=n;++i) scanf("%d",&dis[i]);
	if (st==en){printf("0");return 0;}
	if (st>en){int t=st;st=en;en=t;}
	memset(dp,127/3,sizeof(dp));
	dp[st]=0;
	for (int i=st+1;i<=n;++i){
		int pos=st;
		for (int j=i;j>=st;--j){
			if (dis[i]-dis[j]>L3){pos=j+1;break;}
			int dist=dis[i]-dis[j];
			if (dist<=L1) dp[i]=min(dp[i],dp[j]+C1);
			if (dist>L1&&dist<=L2) dp[i]=min(dp[i],dp[j]+C2);
			if (dist>L2&&dist<=L3) dp[i]=min(dp[i],dp[j]+C3);
		}
		for (int j=pos;j<i;++j){
			int dist=dis[i]-dis[j];
			if (dist<=L1) dp[j]=min(dp[j],dp[i]+C1);
			if (dist>L1&&dist<=L1) dp[j]=min(dp[j],dp[i]+C2);
			if (dist>L2&&dist<=L3) dp[j]=min(dp[j],dp[i]+C3);
		}
	}
	printf("%d",dp[en]);
	return 0;
}