Problem 26299 --【递推】数字三角形(例题)

26299: 【递推】数字三角形(例题)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 37  Solved: 31
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][44kb]

Description


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

                                    

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

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

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

    测试数据通过键盘逐行输入,如上例数据应以如下所示格式输入:

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

Input

    第一行,正整数n,表示数字三角形的行数,n100;

    接下来共n行,第i行(1in)有i个正整数,所有整数介于0~99之间。

Output

    最大的数字和。

Sample Input

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

Sample Output

30

HINT

Source

[Submit][Status]