← 返回题目列表

AtCoder · wupc2012_4

D. 三角拼图

中文机器翻译题面 查看原题
 就在这时,压缩文件的解压似乎完成了。打开一看,这次发现了一个包含直角三角形排列数列的文本文件。

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 请按行输出。

部分点

在满分 100 分中,50 分部分是,N ≦ 20 很满意。

入力例 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 选择 是最优的。