Problem 22500 -- 数字三角形 问题

22500: 数字三角形 问题

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

Description

给定一个由 n 行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形

的顶至底的一条路径,使该路径经过的数字总和最大。


 


«编程任务:

对于给定的由 n 行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数

字和的最大值。 

Input

1 行是数字三角形的行数 n1<=n<=100。接下

来 n 行是数字三角形各行中的数字。所有数字在 0..99 之间。 

Output

将计算结果输出,

第 1 行中的数是计算

出的最大值。 

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]