题目描述：
有一栋楼有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 阅读(498)
评论(0) 编辑 收藏 引用 所属分类:
Problem Solving