青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(855) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲国产成人在线播放| 久久高清福利视频| 亚洲在线一区二区| 影视先锋久久| 一本色道综合亚洲| 一区精品久久| 制服丝袜激情欧洲亚洲| 一区二区在线免费观看| 亚洲理论在线观看| 一区二区三区在线观看欧美 | 136国产福利精品导航网址| 欧美激情视频一区二区三区免费 | 亚洲欧美区自拍先锋| 久久国产天堂福利天堂| 亚洲视频在线一区| 久久中文字幕一区二区三区| 亚洲影音一区| 欧美精品成人一区二区在线观看| 久久一区视频| 国产日韩欧美91| 欧美一区二视频| 久久精品日产第一区二区三区| 久久免费国产精品| 香蕉久久一区二区不卡无毒影院| 欧美成人一区二区| 牛人盗摄一区二区三区视频| 欧美另类综合| 亚洲国产成人一区| 国内精品模特av私拍在线观看| 日韩亚洲国产精品| 亚洲精品视频在线看| 久久亚洲不卡| 欧美 日韩 国产 一区| 国产午夜精品久久| 亚洲女人天堂av| 亚洲女性裸体视频| 欧美午夜视频| 日韩网站免费观看| 亚洲午夜国产成人av电影男同| 欧美激情精品久久久久久黑人 | 久久九九有精品国产23| 欧美一级视频精品观看| 国产精品久久久久毛片大屁完整版 | 欧美r片在线| 美女视频黄免费的久久| 亚洲精品国产精品国自产观看| 欧美精品v日韩精品v韩国精品v| 亚洲美女区一区| 欧美一级播放| 亚洲国产欧美日韩| 欧美三级资源在线| 欧美中文字幕| 亚洲精品社区| 久久精品国产第一区二区三区| 亚洲第一精品夜夜躁人人躁| 欧美精品日韩| 久久精品久久99精品久久| 亚洲激情婷婷| 久久av在线| 亚洲精品乱码久久久久久日本蜜臀| 欧美色播在线播放| 久久久福利视频| 夜夜精品视频| 欧美福利小视频| 午夜在线精品| 日韩亚洲欧美高清| 国产视频亚洲| 欧美日韩免费一区二区三区| 久久久www| 久久天天狠狠| 久久综合图片| 日韩一级黄色av| 老**午夜毛片一区二区三区| 夜夜嗨一区二区| 在线成人小视频| 国产精品久线观看视频| 欧美波霸影院| 久久精品欧美| 亚洲午夜久久久久久尤物| 亚洲国产欧洲综合997久久| 香蕉久久夜色精品| 亚洲最新在线| 亚洲国产精品一区二区久| 国产欧美精品一区二区色综合| 欧美国产三区| 久久综合色综合88| 久久精品一区二区| 亚洲欧美日韩另类| 一区二区av在线| 亚洲国产欧美日韩精品| 久久在线播放| 欧美亚洲综合久久| 午夜精品久久久久久久久久久久久 | 狼狼综合久久久久综合网| 亚洲欧美怡红院| 一本色道久久综合亚洲精品按摩| 永久免费视频成人| 国语自产精品视频在线看一大j8| 国产精品欧美日韩一区| 欧美午夜一区二区福利视频| 欧美日韩国产免费| 欧美精品少妇一区二区三区| 免费观看一级特黄欧美大片| 久久久精品五月天| 久久av一区二区三区漫画| 午夜欧美不卡精品aaaaa| 亚洲一区二区精品视频| 中日韩高清电影网| 亚洲一区二区免费视频| 亚洲影院在线| 香蕉久久国产| 久久精品国产精品 | 99国产精品视频免费观看| 国产精品入口日韩视频大尺度| 欧美久久影院| 国产精品videosex极品| 国产精品九九| 国产欧美日韩在线播放| 国产视频亚洲| 影音国产精品| 日韩视频永久免费观看| 亚洲视频播放| 欧美在现视频| 免费中文字幕日韩欧美| 亚洲大片一区二区三区| 亚洲激情视频在线播放| 一本色道久久综合亚洲91| 亚洲一区在线免费| 久久精品91久久久久久再现| 国产毛片久久| 一区二区三区四区五区视频| 一区二区三区视频观看| 亚洲欧美精品一区| 久久亚洲精品一区二区| 欧美激情国产高清| 国产精品亚洲一区| 精品成人一区二区三区四区| 亚洲啪啪91| 午夜伦理片一区| 美女91精品| 99国产精品久久久久久久久久| 亚洲一区www| 久久在线免费观看| 国产精品久久久久9999高清| 国产一区二区三区四区三区四| 亚洲国产精品一区在线观看不卡| 中国av一区| 久久中文精品| 亚洲一区二区三区成人在线视频精品| 久久成人久久爱| 欧美日韩视频在线第一区| 国产亚洲毛片在线| 老司机一区二区三区| 免费成人高清视频| 亚洲精品欧美专区| 久久aⅴ乱码一区二区三区| 欧美高清不卡| 激情欧美日韩一区| 亚洲欧美精品一区| 亚洲国产精品v| 欧美在线一二三四区| 欧美日韩免费在线视频| 精品96久久久久久中文字幕无| 一区二区三区精品视频| 美腿丝袜亚洲色图| 亚洲视频精选| 欧美另类在线观看| 亚洲国产精品视频| 久久婷婷久久一区二区三区| 一区二区三区视频免费在线观看| 美女黄色成人网| 激情久久久久久久| 欧美一级一区| 亚洲性图久久| 欧美性猛交99久久久久99按摩| 亚洲国产综合视频在线观看| 欧美在线视频在线播放完整版免费观看| 亚洲激情六月丁香| 欧美jizzhd精品欧美喷水| **欧美日韩vr在线| 欧美精品免费在线| 亚洲永久字幕| 欧美激情片在线观看| 在线成人www免费观看视频| 欧美在线视频全部完| 亚洲一卡久久| 国产精品人人爽人人做我的可爱| 一区二区三区精品国产| 亚洲日本中文字幕| 欧美精品在线一区二区| 日韩午夜精品视频| 亚洲日本中文字幕区| 欧美精品日韩精品| 99视频有精品| aa成人免费视频| 国产精品日韩久久久久| 久久不射网站| 久久精品一区二区国产| 永久免费视频成人| 欧美黑人在线观看|