coreBugZJ

此 blog 已棄。

EOJ 1823 數(shù)塔II （動態(tài)規(guī)劃入門）

/*
2

EOJ 1823 數(shù)塔II
3

----問題描述：
6

有一個(gè)由正整數(shù)組成的三角形，
8

第一行只有一個(gè)數(shù)，
9

除了最下行之外每個(gè)數(shù)的左下方和右下方各有一個(gè)數(shù)，
10

如下圖所示：
12

1
14

3 2
15

4 10 1
16

4 3 2 20
17

從第一行的數(shù)開始，除了某一次可以走到下一行的任意位置外，
19

每次都只能左下或右下走一格，
20

直到走到最下行，
21

把沿途經(jīng)過的數(shù)全部加起來，如何走，使得這個(gè)和盡量大？
22

----輸入：
25

輸入數(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

----輸出：
32

對于每個(gè)測試實(shí)例，輸出可能得到的最大和。
34

----樣例輸入：
37

1
39

4
40

1
41

3 2
42

4 10 1
43

4 3 2 20
44

----樣例輸出：
47

34
49

*/
52

/************************************************************************
55

----方案三：
57

方案二的空間優(yōu)化，
59

實(shí)際數(shù)據(jù)范圍只有 25 ；
60

使用滾動數(shù)組。
61

*/
63

/*
64

#include <stdio.h>
65

#define L 25
67

int a[L][L], f[L], h[L];
69

int 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

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

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

則
113

h[i][j] = a[i][j] + max( h[i+1][j], h[i+1][j+1] )
114

f[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

124

int a[L][L], f[L][L], h[L][L];
125

126

int 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

則
169

h[i][j] = a[i][j] + max( h[i-1][j-1], h[i-1][j] )
170

f[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

180

int a[L][L], f[L][L], h[L][L];
181

182

int 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 閱讀(853) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè)

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營技術(shù)類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1823 數(shù)塔II （動態(tài)規(guī)劃入門）