问题 1017 --数字三角形

1017: 数字三角形

时间限制: 1 Sec  内存限制: 128 MB
提交: 19  解决: 13  分值: 20
[提交][记录][讨论版][命题人:]

题目描述

数字三角形,从三角形顶部往下走,只能往左下或右下走,求走到最下面时所经过的数字和最大为多少?(下图为n=6时的情况)







2








96
30






83
52
60




21
65
44
61


8
79
50
41
21
61
41
50
38
79
10

输入

第1行:整数n(1<=n<=1000)

第2-n+1行:每行若干整数,第i行有i-1个整数空格分隔。

输出

一行:一个整数,表示所经过数字的最大和。

样例输入

6
2
96 30
83 52 60
21 65 44 61
8  79 50 41 21
61 41 50 38 79 10

样例输出

375

提示

来源

[提交][记录]