我可以在0101的OJ里,刷一整天的题!—— by 仔仔

11409: 数字三角形

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:3 Solved:0

Description

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







2








96
30






83
52
60




21
65
44
61


8
79
50
41
21
61
41
50
38
79
10

Input

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

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

Output

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

Sample Input Copy

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

Sample Output Copy

375