Problem1820--数塔问题

1820: 数塔问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

      有形如图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大。

Input

第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。

Output

输出可能得到的最大和

Sample Input Copy

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

Sample Output Copy

max=30

Source/Category