Description
一个铁路线上有n(
2<=n<=
10000)个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示：
站之间的距离 - X 票价
0L1L2其中L1，L2，L3，C1，C2，C3都是已知的正整数，且(
1 <= L1 < L2 < L3 <=
10^
9,
1 <= C1 < C2 < C3 <=
10^
9)。显然若两站之间的距离大于L3，那么从一站到另一站至少要买两张票。注意：每一张票在使用时只能从一站开始到另一站结束。现在需要你对于给定的线路，求出从该线路上的站A到站B的最少票价。你能做到吗？
Input
输入文件的第一行为
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
输出文件中只有一个数字,表示从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]:=min(f[i],f[j]+v)，f[i]表示A到B花费的钱数。
const
maxn=
10000;
var
f,t:
array[
1..maxn]
of longint;
l,c:
array[
1..
3]
of longint;
n,a,b,i,j,u,v:longint;
function min(x,y:longint):longint;
begin
if x>y
then exit(y)
else exit(x);
end;
begin
for i:=
1 to 3 do read(l[i]);
for i:=
1 to 3 do read(c[i]);
readln;
readln(n);
readln(a,b);
for i:=
1 to n
do f[i]:=maxlongint;
f[a]:=
0;
t[
1]:=
0;
for i:=
2 to n
do readln(t[i]);
for i:=a+
1 to b
do
for j:=i-
1 downto a
do
begin
u:=t[i]-t[j];
if u<=l[
1]
then v:=c[
1]
else if u<=l[
2]
then v:=c[
2]
else if u<=l[
3]
then v:=c[
3]
else break;
f[i]:=min(f[i],f[j]+v);
end;
write(f[b]);
end.
转载请注明原文地址: https://ju.6miu.com/read-12884.html
