題目描述：
有一棟樓有N（1<=N<=100）層，每層房間有M個房間（1<=M<=500）。每間房間有一個訪問開銷。從一個房間可以到其周邊（上一層同一號，同一層左右兩間）。現在要從一樓開始一直訪問到頂樓，問怎樣走可以獲得最小的訪問開銷？
解題思路：
雙向DP。從一樓到頂樓依次計算從底樓到某一間房子的最小開銷。
技巧點：對于某一層，先計算從下一層或左邊向右走的最小開銷，再嘗試從右邊走到左邊，看是不是開銷可以變小，是則更新。
程序代碼：
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-1-15 9:31:18
4 Problem Source:
5 Description:
6 中間WA了兩次，查了很久，
7 最后發現題目描述的是最多M層，每層最多N間房，原來弄反了！是個不小的教訓
8 ********************************************************************/
9
10 # include <iostream>
11 using namespace std;
12
13 # define MAX 2000000005
14 # define N 555
15 # define M 111
16
17 int n,m;
18 long fee[ M ][ N ], f[ M ][ N ];;
19 int road[ M ][ N ];
20
21 void init()
22 {
23 scanf( "%d %d", &n, &m );
24 for ( int i = 1; i <= n; i ++ )
25 {
26 for ( int j = 1; j <= m; j ++ )
27 {
28 scanf( "%d", &fee[ i ][ j ] );
29 }
30 }
31 }
32
33 void output()
34 {
35 int min = MAX, s = 1;
36 for ( int i = 1; i <= m; i ++ )
37 {
38 if ( f[ n ][ i ] < min )
39 {
40 min = f[ n ][ i ];
41 s = i;
42 }
43 }
44 int step[ n*m+1 ];
45 step[0] = s; s=0;
46 int floor = n;
47 while ( floor > 1 )
48 {
49 s ++;
50 step[ s ] = road[ floor ][ step[s-1] ];
51 if ( step[ s ] == step[ s-1 ] ) floor --;
52 }
53
54 for ( int i = s; i >= 0; i -- )
55 {
56 printf( "%d\n", step[ i ] );
57 }
58 }
59
60 void dp()
61 {
62 int tmp;
63 for ( int i = 1; i <= m; i ++ )
64 {
65 road[1][ i ] = i;
66 f[1][ i ] = fee[1][ i ];
67 }
68 for ( int floor = 2; floor <= n; floor ++ )
69 {
70 f[ floor ][1] = f[ floor-1 ][ 1 ] + fee[ floor ][ 1 ];
71 road[ floor ][1] = 1;
72
73 for ( int i = 2; i <= m; i ++ )
74 {
75 f[ floor ][ i ] = fee[ floor ][ i ];
76 if ( f[ floor ][ i-1 ] < f[ floor-1 ][ i ] )
77 {
78 f[ floor ][ i ] += f[ floor ][ i-1 ];
79 road[ floor ][ i ] = i-1;
80 }
81 else
82 {
83 f[ floor ][ i ] += f[ floor-1 ][ i ];
84 road[ floor ][ i ] = i;
85 }
86 }
87
88 for ( int i = m-1; i > 0; i -- )
89 {
90 tmp = f[ floor ][ i+1 ] + fee[ floor ][ i ];
91 if ( tmp < f[ floor ][ i ] )
92 {
93 f[ floor ][ i ] = tmp;
94 road[ floor ][ i ] = i+1;
95 }
96 }
97 }
98 }
99
100 int main()
101 {
102 int n,m;
103 init();
104 dp();
105 output();
106 return 0;
107 }
108
109
posted on 2008-01-15 11:10
R2 閱讀(510)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving