[動態規劃]Ural 1031 rail 火車票 解題報告

【題目描述】
現在有一條“葉卡特琳堡－斯維爾德洛夫斯克”鐵路線。它有若干個火車站。這個鐵路線可以用一條線段來表示，而火車站就是線段上的點。鐵路起始於葉卡特琳堡(Eakterinburg)，終止於斯維爾德洛夫斯克(Sverlovsk)，且各站從葉卡特琳堡(它的編號是1)至斯維爾德洛夫斯克(終點)編號。

兩個站之間的票價僅跟兩站間的距離有關係。票價規定如下表。

兩站間距離 - X	票價
0<X<=L1	C1
L1<X<=L2	C2
L2<X<=L3	C3

當且僅當兩站間距離不大於L3時才能購買這兩站之間的直達車票。所以有時須要購買若干張票來完成整個旅行。


例如，在上圖，整條鐵路有七個站。從第2站不能直達第6站(因為距離大於L3)，但有另外幾種方法購票。其中一種是買兩張票：一張是從第2站至第3 站(票價為C2)，另一張是從第3站至第6站(票價為C3)，注意，雖然從第2站至第6站的距離為2×L2，但不可以買兩張價值C2的票，因為一張票只可以用一次且起點和終點必須在車站上。

你的任務時計算給出的兩站之間的最小花費。

輸入

輸入的第一行包含六個由空格隔開的整數L1，L2，L3，C1，C2，C3(1<=L1<L2<L3<=10^9，1& lt;=C1<C2<C3<=10^9)。第二行為車站數N(2<=N<=10000)。第三行有兩個由空格隔開的不等的整數，表示旅行起點和終點。接下來的N-1行為起點(葉卡特琳堡)至其它站的距離。這些距離為互不相等的正整數而且呈上升序列。從葉卡特琳堡至斯維爾德洛夫斯克的距離不超過10^9。任意兩相鄰站之間的距離不超過L3。旅行最小花費不超過10^9。

輸出

一個整數------最小花費。

樣例輸入

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

樣例輸出

70

【我的代碼】
裸代碼RawCode

C++语言: Codee#25587

01 /*
02 *Problem: Ural 1031 rail
03 *Author: Yee-fan Zhu
04 *Email: zyfworks@gmail.com
05 *Method: Dynamic Programming
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 using namespace std;
10 const int MAXN=10001;
11 typedef unsigned long long ull;
12 ull L[4];
13 ull Cost[4];
14 ull dist[MAXN];
15 ull F[MAXN];
16 int S,T;
17 int N;
18
19 void init()
20 {
21     for(int i=1;i<=3;i++) scanf("%d",&L[i]);
22     for(int i=1;i<=3;i++) scanf("%d",&Cost[i]);
23     scanf("%d\n",&N);
24     scanf("%d %d\n",&S,&T);
25     if(S>T){int t=S;S=T;T=t;}
26     if(S==T) {printf("0\n");exit(0);}
27     dist[1]=0;
28     for(int i=2;i<=N;i++) scanf("%d\n",&dist[i]);
29 }
30
31 ull Min(ull a,ull b)
32 {
33     return a<b?a:b;
34 }
35
36 void dp()
37 {
38     F[S]=0;
39     for(int i=S+1;i<=T;i++)
40     {
41         F[i]=2000000000;
42         int k=i-1;
43         ull delta;
44         for(;k>=S;k--)
45         {
46             delta=dist[i]-dist[k];
47             if(delta>L[3])
48                 break;
49             if(delta<=L[1])
50             {
51                 F[i]=Min(F[i],F[k]+Cost[1]);
52                 continue;
53             }
54             if(delta<=L[2])
55             {
56                 F[i]=Min(F[i],F[k]+Cost[2]);
57                 continue;
58             }
59             F[i]=Min(F[i],F[k]+Cost[3]);
60         }
61     }
62     printf("%d\n",F[T]);
63 }
64
65 int main()
66 {
67     freopen("rail.in","r",stdin);
68     freopen("rail.out","w",stdout);
69     init();
70     dp();
71     return 0;
72 }