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





            
	    
    




            






            

				

            


    
    







            
	   
	



精品久久久久成人码免费动漫|
久久久久噜噜噜亚洲熟女综合|
国产精品欧美久久久久无广告|
色婷婷综合久久久久中文|
久久久久亚洲AV成人网人人软件
|
久久久久无码国产精品不卡|
狠狠色丁香久久婷婷综合蜜芽五月|
激情久久久久久久久久|
国产Av激情久久无码天堂|
无码日韩人妻精品久久蜜桃
|
久久综合日本熟妇|
久久精品中文騷妇女内射|
久久久久高潮综合影院|
一本久久a久久精品vr综合|
伊人久久五月天|
国产精品久久久香蕉|
亚洲国产美女精品久久久久∴|
久久SE精品一区二区|
色婷婷综合久久久久中文一区二区
|
久久综合一区二区无码|
色婷婷久久久SWAG精品|
久久亚洲国产最新网站|
人妻无码αv中文字幕久久|
久久亚洲精品成人av无码网站|
久久精品毛片免费观看|
欧美综合天天夜夜久久|
久久久WWW免费人成精品|
最新久久免费视频|
中文字幕亚洲综合久久|
国产精品无码久久久久|
色婷婷久久综合中文久久一本|
久久免费看黄a级毛片|
久久久噜噜噜久久中文福利|
91精品久久久久久无码|
伊人伊成久久人综合网777|
国内高清久久久久久|
久久婷婷国产麻豆91天堂|
久久人人爽人人爽人人片AV东京热|
99精品国产99久久久久久97|
国产精品久久久久久久久|
久久无码精品一区二区三区|