问题 22119 --数塔问题

22119: 数塔问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 59  解决: 41
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

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

输入

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

输出

输出可能得到的最大和

样例输入

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

样例输出

max=30

提示

来源

[提交][状态]