问题 2596 --数字三角形

2596: 数字三角形

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

题目描述

数字三角形,从三角形顶部往下走,只能往左下或右下走,求走到最下面时所经过的数字和最大为多少?(下图为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

提示

来源

[提交][状态]