• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 1823 數(shù)塔II        （動態(tài)規(guī)劃入門）
		
            
		
            

              1/*
              2EOJ 1823 數(shù)塔II
              3
              4
              5----問題描述：
              6
              7有一個(gè)由正整數(shù)組成的三角形，
              8第一行只有一個(gè)數(shù)，
              9除了最下行之外每個(gè)數(shù)的左下方和右下方各有一個(gè)數(shù)，
             10
             11如下圖所示：
             12
             13         1
             14       3   2
             15     4  10   1
             16   4   3   2  20
             17
             18從第一行的數(shù)開始，除了某一次可以走到下一行的任意位置外，
             19每次都只能左下或右下走一格，
             20直到走到最下行，
             21把沿途經(jīng)過的數(shù)全部加起來，如何走，使得這個(gè)和盡量大？
             22
             23
             24----輸入：
             25
             26輸入數(shù)據(jù)首先包括一個(gè)整數(shù) C，表示測試實(shí)例的個(gè)數(shù)，
             27每個(gè)測試實(shí)例的第一行是一個(gè)整數(shù) N （1 <= N <= 500），表示數(shù)塔的高度，
             28接下來用 N 行數(shù)字表示數(shù)塔，其中第 i 行有 i 個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間 [ 0, 99 ] 內(nèi)。
             29
             30
             31----輸出：
             32
             33對于每個(gè)測試實(shí)例，輸出可能得到的最大和。
             34
             35
             36----樣例輸入：
             37
             381
             394
             401
             413 2
             424 10 1
             434 3 2 20
             44
             45
             46----樣例輸出：
             47
             4834
             49
             50
             51*/
             52
             53
             54/************************************************************************
             55
             56----方案三：
             57
             58方案二的空間優(yōu)化，
             59實(shí)際數(shù)據(jù)范圍只有 25 ；
             60使用滾動數(shù)組。
             61
             62*/
             63/*
             64#include <stdio.h>
             65
             66#define  L  25
             67
             68int a[L][L], f[L], h[L];
             69
             70int main(){
             71        int td, n, i, j, ans, tmp;
             72        scanf( "%d", &td );
             73        while( td-- ){
             74                scanf( "%d", &n );
             75                for( i=1; i<=n; ++i ){
             76                        for( j=1; j<=i; ++j ){
             77                                scanf( "%d", &a[i][j] );
             78                        }
             79                }
             80
             81                for( j=1; j<=n; ++j ){
             82                        f[j] = h[j] = a[n][j];
             83                }
             84                for( i=n-1; i>0; --i ){
             85                        tmp = h[i+1];
             86                        for( j=1; j<=i; ++j ){
             87                                tmp = ( tmp < h[j] ? h[j] : tmp );
             88                        }
             89                        for( j=1; j<=i; ++j ){
             90                                h[j] = a[i][j] + ( h[j] > h[j+1] ? h[j] : h[j+1] );
             91                                f[j] = a[i][j] + ( f[j] > f[j+1] ? f[j] : f[j+1] );
             92                                f[j] = ( (tmp+a[i][j]) > f[j] ? (tmp+a[i][j]) : f[j] );
             93                        }
             94                }
             95
             96                ans = f[1];
             97                printf( "%d\n", ans );
             98        }
             99        return 0;
            100}
            101*/
            102
            103
            104/************************************************************************
            105
            106----方案二
            107
            108令 a[i][j] 表示第 i 行第 j 個(gè)數(shù)字，（1 <= j <= i <= n）；
            109令 h[i][j] 表示從 a[i][j] 開始走到最后一行所能得到的最大和，其中每次都只能左下或右下走一格；
            110令 f[i][j] 表示從 a[i][j] 開始走到最后一行所能得到的最大和，其中某一次走到了下一行的任意位置；
            111
            112則
            113h[i][j] = a[i][j] + max( h[i+1][j], h[i+1][j+1] )
            114f[i][j] = a[i][j] + max( f[i+1][j], f[i+1][j+1], h[i+1][k] )  其中 1 <= k <= i+1
            115
            116結(jié)果為 f[1][1]。
            117
            118*/
            119/*
            120#include <stdio.h>
            121
            122#define  L  503
            123
            124int a[L][L], f[L][L], h[L][L];
            125
            126int main(){
            127        int td, n, i, j, ans, tmp;
            128        scanf( "%d", &td );
            129        while( td-- ){
            130                scanf( "%d", &n );
            131                for( i=1; i<=n; ++i ){
            132                        for( j=1; j<=i; ++j ){
            133                                scanf( "%d", &a[i][j] );
            134                        }
            135                }
            136
            137                for( j=1; j<=n; ++j ){
            138                        f[n][j] = h[n][j] = a[n][j];
            139                }
            140                for( i=n-1; i>0; --i ){
            141                        tmp = h[i+1][i+1];
            142                        for( j=1; j<=i; ++j ){
            143                                tmp = ( tmp < h[i+1][j] ? h[i+1][j] : tmp );
            144                        }
            145                        for( j=1; j<=i; ++j ){
            146                                h[i][j] = a[i][j] + ( h[i+1][j] > h[i+1][j+1] ? h[i+1][j] : h[i+1][j+1] );
            147                                f[i][j] = a[i][j] + ( f[i+1][j] > f[i+1][j+1] ? f[i+1][j] : f[i+1][j+1] );
            148                                f[i][j] = ( (tmp+a[i][j]) > f[i][j] ? (tmp+a[i][j]) : f[i][j] );
            149                        }
            150                }
            151
            152                ans = f[1][1];
            153                printf( "%d\n", ans );
            154        }
            155        return 0;
            156}
            157*/
            158
            159
            160/************************************************************************
            161
            162----方案一
            163
            164令 a[i][j] 表示第 i 行第 j 個(gè)數(shù)字，（1 <= j <= i <= n）；
            165令 h[i][j] 表示從第一行的數(shù)開始走到 a[i][j] 所能得到的最大和，其中每次都只能左下或右下走一格；
            166令 f[i][j] 表示從 a[i][j] 開始走到最后一行所能得到的最大和，每次都只能左下或右下走一格；
            167
            168則
            169h[i][j] = a[i][j] + max( h[i-1][j-1], h[i-1][j] )
            170f[i][j] = a[i][j] + max( f[i+1][j], f[i+1][j+1] )
            171
            172結(jié)果為 max( h[i][j], f[i+1][k] ) 。
            173
            174*/
            175/*
            176#include <stdio.h>
            177
            178#define  L  503
            179
            180int a[L][L], f[L][L], h[L][L];
            181
            182int main(){
            183        int td, n, i, j, k, ans;
            184        scanf( "%d", &td );
            185        while( td-- ){
            186                scanf( "%d", &n );
            187                for( i=1; i<=n; ++i ){
            188                        for( j=1; j<=i; ++j ){
            189                                scanf( "%d", &a[i][j] );
            190                        }
            191                }
            192
            193                for( j=1; j<=n; ++j ){
            194                        f[n][j] = a[n][j];
            195                }
            196                for( i=n-1; i>0; --i ){
            197                        for( j=1; j<=i; ++j ){
            198                                f[i][j] = a[i][j] + ( f[i+1][j] > f[i+1][j+1] ? f[i+1][j] : f[i+1][j+1] );
            199                        }
            200                }
            201
            202                h[1][1] = a[1][1];
            203                for( i=2; i<=n; ++i ){
            204                        h[i][1] = a[i][1] + h[i-1][1];
            205                        h[i][i] = a[i][i] + h[i-1][i-1];
            206                        for( j=2; j<i; ++j ){
            207                                h[i][j] = a[i][j] + ( h[i-1][j-1] > h[i-1][j] ? h[i-1][j-1] : h[i-1][j] );
            208                        }
            209                }
            210
            211                ans = f[1][1];
            212                for( i=1; i<n; ++i ){
            213                        for( j=1; j<=i; ++j ){
            214                                for( k=i+1; k>0; --k ){
            215                                        if( h[i][j] + f[i+1][k] > ans ){
            216                                                ans = h[i][j] + f[i+1][k];
            217                                        }
            218                                }
            219                        }
            220                }
            221
            222                printf( "%d\n", ans );
            223        }
            224        return 0;
            225}
            226*/
            227
            
		
            
			posted on 2012-03-16 12:02 coreBugZJ 閱讀(828) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



热久久最新网站获取|
亚洲综合精品香蕉久久网97|
国产精品99久久不卡|
久久国产高清一区二区三区|
国产成人综合久久精品红|
亚洲伊人久久大香线蕉综合图片|
精品少妇人妻av无码久久|
国产福利电影一区二区三区久久老子无码午夜伦不
|
精品熟女少妇aⅴ免费久久|
久久人妻无码中文字幕|
久久精品天天中文字幕人妻|
精品久久久久久国产牛牛app
|
久久精品国产亚洲av麻豆色欲|
亚洲国产精品久久久久网站|
99久久香蕉国产线看观香|
2022年国产精品久久久久|
久久久黄色大片|
久久本道久久综合伊人|
久久免费小视频|
波多野结衣中文字幕久久|
伊人久久成人成综合网222|
久久免费美女视频|
国产美女久久精品香蕉69|
久久综合久久综合亚洲|
精品综合久久久久久88小说
|
久久国产精品波多野结衣AV|
久久精品午夜一区二区福利|
精品综合久久久久久97|
中文字幕亚洲综合久久菠萝蜜|
国产精品伊人久久伊人电影|
久久电影网一区|
MM131亚洲国产美女久久|
亚洲午夜久久久久妓女影院|
武侠古典久久婷婷狼人伊人|
日本精品久久久久影院日本|
精品欧美一区二区三区久久久|
精品国产91久久久久久久|
国产∨亚洲V天堂无码久久久|
久久人人爽人人爽人人AV
|
日本WV一本一道久久香蕉|
人人狠狠综合久久亚洲高清|