Posted on 2008-08-20 14:57
Hero 阅读(186)
评论(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 }