coreBugZJ

此 blog 已棄。

EOJ 1823 數塔II （動態規劃入門）

/*
2

EOJ 1823 數塔II
3

----問題描述：
6

有一個由正整數組成的三角形，
8

第一行只有一個數，
9

除了最下行之外每個數的左下方和右下方各有一個數，
10

如下圖所示：
12

1
14

3 2
15

4 10 1
16

4 3 2 20
17

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

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

直到走到最下行，
21

把沿途經過的數全部加起來，如何走，使得這個和盡量大？
22

----輸入：
25

輸入數據首先包括一個整數 C，表示測試實例的個數，
27

每個測試實例的第一行是一個整數 N （1 <= N <= 500），表示數塔的高度，
28

接下來用 N 行數字表示數塔，其中第 i 行有 i 個整數，且所有的整數均在區間 [ 0, 99 ] 內。
29

----輸出：
32

對于每個測試實例，輸出可能得到的最大和。
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

方案二的空間優化，
59

實際數據范圍只有 25 ；
60

使用滾動數組。
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 個數字，（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

結果為 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 個數字，（1 <= j <= i <= n）；
165

令 h[i][j] 表示從第一行的數開始走到 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

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

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


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1823 數塔II （動態規劃入門）