• <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 數塔II        （動態規劃入門）
		
            
		
            

              1/*
              2EOJ 1823 數塔II
              3
              4
              5----問題描述：
              6
              7有一個由正整數組成的三角形，
              8第一行只有一個數，
              9除了最下行之外每個數的左下方和右下方各有一個數，
             10
             11如下圖所示：
             12
             13         1
             14       3   2
             15     4  10   1
             16   4   3   2  20
             17
             18從第一行的數開始，除了某一次可以走到下一行的任意位置外，
             19每次都只能左下或右下走一格，
             20直到走到最下行，
             21把沿途經過的數全部加起來，如何走，使得這個和盡量大？
             22
             23
             24----輸入：
             25
             26輸入數據首先包括一個整數 C，表示測試實例的個數，
             27每個測試實例的第一行是一個整數 N （1 <= N <= 500），表示數塔的高度，
             28接下來用 N 行數字表示數塔，其中第 i 行有 i 個整數，且所有的整數均在區間 [ 0, 99 ] 內。
             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方案二的空間優化，
             59實際數據范圍只有 25 ；
             60使用滾動數組。
             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 個數字，（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結果為 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 個數字，（1 <= j <= i <= n）；
            165令 h[i][j] 表示從第一行的數開始走到 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結果為 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 閱讀(847) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久精品国产男包|
国产麻豆精品久久一二三|
久久伊人精品一区二区三区|
久久久久久精品免费免费自慰|
久久综合国产乱子伦精品免费|
99精品久久精品|
香蕉久久永久视频|
国产成人精品久久免费动漫|
亚洲一区精品伊人久久伊人|
久久免费小视频|
人妻少妇久久中文字幕|
久久亚洲精品无码播放|
久久精品国产一区二区三区日韩|
国产99久久久国产精品小说|
伊人久久大香线蕉影院95|
久久99国内精品自在现线|
精品多毛少妇人妻AV免费久久|
国产精品熟女福利久久AV|
久久这里只精品国产99热|
久久成人国产精品|
久久精品国产亚洲AV影院|
性欧美大战久久久久久久
|
亚洲国产精品无码久久久不卡
|
99国产欧美久久久精品蜜芽|
一本色道久久综合狠狠躁|
久久久亚洲精品蜜桃臀|
国产精品热久久毛片|
国产99久久久久久免费看|
99久久精品九九亚洲精品|
国产成人久久久精品二区三区|
青青青伊人色综合久久|
AA级片免费看视频久久|
99久久亚洲综合精品成人|
久久伊人精品青青草原高清|
久久精品国产99国产精品澳门|
99麻豆久久久国产精品免费
|
青青青青久久精品国产|
青青国产成人久久91网|
狠狠人妻久久久久久综合|
久久综合久久伊人|
久久精品人人做人人爽电影|