7
2 3
1 5 4
看起来,这是一个问题:从最上面的顶点开始,每次可以选择下一行的正下方或右下方,到达底边时,求路径中数值总和的最大值。如果是这样,那很简单。在上面的例子中,选择 7 -> 3 -> 5 是最优的,总和为 15。但是,这样的文件有很多,有些数据甚至高达100行。不解决这个问题就没有资格参加…?
不,对,这是一封编程竞赛的邀请函。只要写一个程序,输入数列就能求出最大值就行了。大概,发出邀请函的人正是期待这个结果。
問題文
例如,如果给定如下数列,
3
7 4
2 4 6
8 5 9 3
正确选择的情况下,
3
7 4
2 4 6
8 5 9 3
并且总和为 3 + 7 + 4 + 9 = 23。
入力
N
a_{1,1}
a_{2,1} a_{2,2}
a_{3,1} a_{3,2} a_{3,3}
...
a_{i,1} a_{i,2} ... a_{i,i}
...
a_{N,1} a_{N,2} ... a_{N,N}
- 1 行号表示直角三角形的高度 N(1 ≦ N ≦ 100)。
- i 行目(2 ≦ i ≦ N+1每行的数字以半角空格分隔 i-1 。
- 数列中包含的数字为 0 ≦ a_{i,j} ≦ 100(1 ≦ j ≦ i ≦ N)满意。
出力
部分点
入力例 1
1 3
出力例 1
3
入力例 2
3 7 2 3 1 5 4
出力例 2
15
入力例 3
4 1 8 2 3 2 9 1 1 4 2
出力例 3
16
- 1 -> 2 -> 9 -> 4 选择 是最优的。