Posted on 2008-08-20 14:57
Hero 閱讀(192)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // URAL 1031 C++ Accepted 0.015 377 KB
2
3 //DP--只有3中狀態的DP--posi[][]用于預處理
4 //1. 起點可以大于終點的--特別要注意
5 //2. 在DP的時候要注意posi[i][j]==i(自身)的時候的情況
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 typedef unsigned int unint ;
11 typedef unsigned long long unllong ;
12 const unint INF = 30e8 ;
13
14 const int size = 10010 ;
15 int len[3] ;//收費長度標準
16 int cost[3] ;//對應的費用
17
18 int posi[size][3] ;//記錄當前狀態的三個前序狀態位置
19 unllong dp[size] ;//記錄當前位置的最優值
20
21 int inn ;//車站的個數
22 int sn, en ;//起點--終點
23 int dist[size] ;
24
25 void input()
26 {
27 scanf( "%d %d %d", &len[0], &len[1], &len[2] ) ;
28 scanf( "%d %d %d", &cost[0], &cost[1], &cost[2] ) ;
29
30 scanf( "%d", &inn ) ; scanf( "%d %d", &sn, &en ) ;
31 if( sn > en ) { int temp = sn ; sn = en ; en = temp ; }
32 for( int i=2; i<=inn; i++ ) scanf( "%d", &dist[i] ) ;
33 }
34
35 void process()
36 {
37 for( int way=0; way<3; way++ )
38 {//預處理--找到當前狀態i的上一個狀態位置
39 int curn = en-1 ;//指針
40 for( int i=en; i>sn; i-- )
41 {
42 while( dist[i]-dist[curn]<=len[way] && curn>=sn ) curn-- ;
43 posi[i][way] = curn+1 ;
44 }
45 }
46
47 dp[sn] = 0 ;
48 for( int i=sn+1; i<=en; i++ )
49 {
50 dp[i] = size*INF ;
51 for( int j=0; j<3; j++ )
52 {
53 if( /*posi[i][j] != i &&*/ dp[i] > dp[posi[i][j]] + cost[j] )
54 dp[i] = dp[posi[i][j]] + cost[j] ;
55 }
56 }
57 }
58
59 void output()
60 {
61 printf( "%llu\n", dp[en] ) ;
62 }
63
64 int main()
65 {
66 input() ;
67
68 process() ;
69
70 output() ;
71
72 return 0 ;
73 }