HUSTOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 B: 数塔游戏——递推实现

内存限制：512 MB 时间限制：1.000 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：172 通过：99
返回比赛提交提交记录

题目描述

•如图1，为一个数字三角形。请编写一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
•1.一步可沿左斜线向下或右斜线向下走；
•2.三角形行数小于等于100；
•三角形中的数字为0,1，…，99；
•测试数据通过键盘逐行输入，如上例数据应以如图2所示格式输入：
•          7                              5
•        3   8                           7
•      8   1   0                        3 8
•    2   7   4   4                     8 1 0
•  4   5   2   6   5                  2 7 4 4
•        图1                             4 5 2 6 5
•                                      图2

输入格式

输入n+1行
第一行输入数塔的层数n
接下来n行依次输入数塔从顶到底每层的数字

输出格式

最大数字和

输入样例 复制 

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例 复制 

30

分类标签