• <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        （動(dòng)態(tài)規(guī)劃入門(mén)）
		
            
		
            

              1/*
              2EOJ 1823 數(shù)塔II
              3
              4
              5----問(wèn)題描述：
              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ù)開(kāi)始，除了某一次可以走到下一行的任意位置外，
             19每次都只能左下或右下走一格，
             20直到走到最下行，
             21把沿途經(jīng)過(guò)的數(shù)全部加起來(lái)，如何走，使得這個(gè)和盡量大？
             22
             23
             24----輸入：
             25
             26輸入數(shù)據(jù)首先包括一個(gè)整數(shù) C，表示測(cè)試實(shí)例的個(gè)數(shù)，
             27每個(gè)測(cè)試實(shí)例的第一行是一個(gè)整數(shù) N （1 <= N <= 500），表示數(shù)塔的高度，
             28接下來(lái)用 N 行數(shù)字表示數(shù)塔，其中第 i 行有 i 個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間 [ 0, 99 ] 內(nèi)。
             29
             30
             31----輸出：
             32
             33對(duì)于每個(gè)測(cè)試實(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使用滾動(dòng)數(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] 開(kāi)始走到最后一行所能得到的最大和，其中每次都只能左下或右下走一格；
            110令 f[i][j] 表示從 a[i][j] 開(kāi)始走到最后一行所能得到的最大和，其中某一次走到了下一行的任意位置；
            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ù)開(kāi)始走到 a[i][j] 所能得到的最大和，其中每次都只能左下或右下走一格；
            166令 f[i][j] 表示從 a[i][j] 開(kāi)始走到最后一行所能得到的最大和，每次都只能左下或右下走一格；
            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) 評(píng)論(0)  編輯 收藏 引用  所屬分類(lèi): ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产精品久久久久久久久免费|
9999国产精品欧美久久久久久
|
色狠狠久久AV五月综合|
色偷偷88888欧美精品久久久|
久久综合久久自在自线精品自|
成人久久综合网|
一级做a爰片久久毛片毛片|
久久亚洲精品成人av无码网站|
蜜臀久久99精品久久久久久小说|
国产精品免费久久久久电影网|
性做久久久久久久|
亚洲&#228;v永久无码精品天堂久久|
无码人妻久久一区二区三区|
久久综合综合久久狠狠狠97色88|
99久久精品国产一区二区
|
久久久久国产|
狠狠色丁香久久婷婷综合五月
|
无码专区久久综合久中文字幕
|
热久久国产精品|
久久午夜羞羞影院免费观看|
亚洲欧洲精品成人久久曰影片|
国产精品伦理久久久久久|
蜜臀av性久久久久蜜臀aⅴ麻豆|
久久人妻少妇嫩草AV无码蜜桃|
国产精品久久久天天影视香蕉|
日韩精品久久久久久久电影蜜臀|
久久99精品久久久久久噜噜
|
AV无码久久久久不卡蜜桃|
久久精品国产第一区二区|
欧美精品一本久久男人的天堂|
久久天天躁狠狠躁夜夜网站|
久久久国产视频|
99久久香蕉国产线看观香|
精品久久人人爽天天玩人人妻|
亚洲国产精品无码久久久不卡|
伊人精品久久久久7777|
色婷婷噜噜久久国产精品12p|
久久久久久亚洲精品无码|
久久久国产精品|
久久福利资源国产精品999|
久久这里只有精品视频99|