• <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有一個由正整數(shù)組成的三角形，
              8第一行只有一個數(shù)，
              9除了最下行之外每個數(shù)的左下方和右下方各有一個數(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ù)全部加起來，如何走，使得這個和盡量大？
             22
             23
             24----輸入：
             25
             26輸入數(shù)據(jù)首先包括一個整數(shù) C，表示測試實例的個數(shù)，
             27每個測試實例的第一行是一個整數(shù) N （1 <= N <= 500），表示數(shù)塔的高度，
             28接下來用 N 行數(shù)字表示數(shù)塔，其中第 i 行有 i 個整數(shù)，且所有的整數(shù)均在區(qū)間 [ 0, 99 ] 內(nèi)。
             29
             30
             31----輸出：
             32
             33對于每個測試實例，輸出可能得到的最大和。
             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ù)據(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 個數(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 個數(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 閱讀(836) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



九九久久99综合一区二区|
国产精品久久久99|
亚洲国产成人久久综合野外|
亚洲欧美国产精品专区久久|
欧美久久久久久|
久久精品中文无码资源站|
久久夜色tv网站|
久久成人小视频|
99久久免费国产精精品|
婷婷久久综合九色综合绿巨人
|
69SEX久久精品国产麻豆|
品成人欧美大片久久国产欧美...|
久久久久九九精品影院|
精品熟女少妇av免费久久|
久久久久久av无码免费看大片|
婷婷五月深深久久精品|
久久久久这里只有精品
|
久久免费观看视频|
亚洲va久久久噜噜噜久久天堂|
久久成人国产精品二三区|
国内精品人妻无码久久久影院导航|
99久久精品国产免看国产一区|
中文字幕精品无码久久久久久3D日动漫
|
69久久夜色精品国产69|
波多野结衣久久一区二区
|
亚洲人成网亚洲欧洲无码久久|
伊人久久免费视频|
久久精品国产清高在天天线|
久久99国产精品久久99小说|
99久久婷婷国产一区二区|
精品久久久久久久|
久久精品国产亚洲av水果派|
亚洲国产精品18久久久久久|
久久天天躁狠狠躁夜夜2020|
久久久久久亚洲精品不卡|
亚洲乱亚洲乱淫久久|
成人国内精品久久久久影院|
久久精品国产亚洲77777|
国内精品伊人久久久久AV影院|
伊人久久大香线蕉综合Av
|
2021最新久久久视精品爱|