数塔问题

提交数: 349, 通过率: 62.46%, 平均分: 63.73

题目描述:

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

　●每一步可沿左斜线向下或右斜线向下走；

　●1＜三角形行数≤100；

　●三角形中的数字为整数0，1，…99； 

 1533535087154526226.png

 

输入格式:

第一行读入三角形的行数。

接下来，给定一个数字三角形。

输出格式:

一个数，最大总和

样例输入:

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

样例输出:

max=30
时间限制: 1000ms
空间限制: 128MB

来源: IOI94