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 阅读(793) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithm课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理