• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>


            May the force be with you!
            posts - 52,  comments - 33,  trackbacks - 0

            題目描述:
                    有一棟樓有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     最后發(fā)現題目描述的是最多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
            你是第 free hit counter 位訪客




            <2007年12月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 63692
            • 排名 - 358

            最新評論

            閱讀排行榜

            評論排行榜

            精品欧美一区二区三区久久久| 亚洲AV无一区二区三区久久| 久久久91精品国产一区二区三区 | 久久精品无码一区二区三区日韩| 久久成人18免费网站| 国产精品久久久久蜜芽| 国产成人综合久久综合| 久久只这里是精品66| 久久一日本道色综合久久| 久久一区二区三区免费| 精品无码久久久久久午夜| 色婷婷综合久久久久中文字幕| 亚洲AV日韩精品久久久久久| 久久97久久97精品免视看秋霞| 亚洲精品乱码久久久久久按摩 | 久久成人国产精品二三区| 青春久久| 精品99久久aaa一级毛片| 亚洲精品无码久久久久久| 久久久久99精品成人片| 国产午夜精品理论片久久影视 | 精品久久久久久国产牛牛app | 三级韩国一区久久二区综合 | 亚洲愉拍99热成人精品热久久| 久久AⅤ人妻少妇嫩草影院| 国产精品久久久久久福利漫画| 国内精品伊人久久久久777| 午夜精品久久久久久| 国产成人无码精品久久久久免费 | 久久久亚洲AV波多野结衣| 性做久久久久久免费观看| 久久久久亚洲AV无码去区首| 久久精品一区二区| 麻豆精品久久久一区二区| 久久免费精品视频| 国产精品久久亚洲不卡动漫| 久久99国产综合精品| 久久精品国产影库免费看| 狠狠色婷婷综合天天久久丁香| 国产精品免费福利久久| 国产精品久久精品|