OpenJudge

2315:数塔问题

总时间限制:
1000ms
内存限制:
65536kB
描述

如图3-1所示为一个数字三角形。请编写一个程序计算从顶到底的某处的一条路径,使该路径所经过的数字的总和最大。只要求输出总和。

1.一步可沿左斜线向下或向右斜线向下走;

2.三角形行数小于等于100;

3.三角形中的数字为0,1,...,99;

测试数据通过键盘逐行输入,如上例数据应以如图3-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

                          图3-1                                                        4 5 2 6 5

                                                                                             图3-2

输入
第一行为数字三角形的行数;
第二行为数字三角形,两个数之间用空格隔开。
输出
所经过数字的最大总和。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
来源
YBT
全局题号
12836
添加于
2017-01-19
提交次数
19
尝试人数
16
通过人数
16