11409: 数字三角形
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:Imported
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