Posted on 2008-08-20 14:57
Hero 閱讀(204)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
代碼如詩(shī)－－ACM
1 // URAL 1031 C++ Accepted 0.015 377 KB
2
3 //DP--只有3中狀態(tài)的DP--posi[][]用于預(yù)處理
4 //1. 起點(diǎn)可以大于終點(diǎn)的--特別要注意
5 //2. 在DP的時(shí)候要注意posi[i][j]==i(自身)的時(shí)候的情況
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] ;//收費(fèi)長(zhǎng)度標(biāo)準(zhǔn)
16 int cost[3] ;//對(duì)應(yīng)的費(fèi)用
17
18 int posi[size][3] ;//記錄當(dāng)前狀態(tài)的三個(gè)前序狀態(tài)位置
19 unllong dp[size] ;//記錄當(dāng)前位置的最優(yōu)值
20
21 int inn ;//車(chē)站的個(gè)數(shù)
22 int sn, en ;//起點(diǎn)--終點(diǎn)
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 {//預(yù)處理--找到當(dāng)前狀態(tài)i的上一個(gè)狀態(tà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 }