火车票

题目背景

题目描述

一个铁路线上有 $n$ 个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示：

站之间的距离 –$X$	票价
$0<X\le L_1$	$C_1$
$L_1<X\le L_2$	$C_2$
$L_2<X\le L_3$	$C_3$
$L_3<X$	$\infty$

注意：每一张票在使用时只能从一站开始到另一站结束，不能在中途结束。

输入格式

第一行为 $6$ 个由空格隔开的整数 $L_1, L_2, L_3, C_1, C_2, C_3\ (1 \le L1 < L2 < L3 \le 10^9, 1 \le C1 < C2 < C3 \le 10^9)$。

第二行为火车站的数量 $n\ (2 \le n \le 10000)$。

第三行为两个不同的整数 $A、B$，由空格隔开。

接下来的 $n-1$ 行包含从第一站到其他站之间的距离，保证这些距离按照增长的顺序被设置为不同的正整数。相邻两站之间的距离不超过 $L_3$. 两个给定火车站之间行程花费的最小值不超过 $10^9$，而且任意两站之间距离不超过 $10^9$。

输出格式

只有一个数字,表示从 $A$ 到 $B$ 要花费的最小值。

样例 #1

样例输入 #1

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

样例输出 #1

70

呱呱泡蛙只有 $80pts$ 求助！！！

code

#include<iostream>
#define int long long 
using namespace std;
int dp[10005] , n , l1 , l2 , l3 , c1 , c2 , c3 , A , B;
int len[10005]; 
signed main(){
	cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3;
	cin >> n >> A >> B;
	for(int i=2;i<=n;i++){
		cin >> len[i];dp[i] = 0x3f3f3f3f;
	}
	if(A>B)swap(A,B);
	dp[A] = 0;
	for(int i=A;i<B;i++){ 
		for(int j=i+1;j<=B;j++){
			int cnt = len[j] - len[i] , tmp;
			if(cnt<=l1)tmp = c1;
			else if(cnt<=l2)tmp = c2;
			else if(cnt<=l3)tmp = c3;
			if(cnt<=l3)dp[j] = min(dp[j],dp[i]+tmp);
		}
	}
	cout << dp[B];
	return 0;
}

求（你认为的）正解+思路，拿分 $80$ 以上就关！求求了QAQ