Problem 22119 --数塔问题

22119: 数塔问题

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

Description

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

Input

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

Output

输出可能得到的最大和

Sample Input

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

Sample Output

max=30

HINT

Source

[Submit][Status]