AT_wupc2012_4 三角パズル

在你忙碌的过程中，压缩文件的解压似乎已经完成了。你打开一看，发现了一个包含按直角三角形排列的数列的文本文件。 例如： 7 2 3 1 5 4 看起来，这是一个从最上方的顶点出发，每次只能选择往下一层的正下方或右下方的数字，直到底边为止，要求出路径上数字之和的最大值的问题。这很简单。在上面的例子中，选择 $7 \to 3 \to 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}$ > $\cdots$ > $a_{i,1}\ a_{i,2}\ \cdots\ a_{i,i}$ > $\cdots$ > $a_{N,1}\ a_{N,2}\ \cdots\ a_{N,N}$ - 第 $1$ 行给出直角三角形的高度 $N$（$1 \leq N \leq 100$）。 - 第 $i$ 行（$2 \leq i \leq N+1$）有 $i-1$ 个用半角空格分隔的整数。 - 数列中的数字满足 $0 \leq a_{i,j} \leq 100$（$1 \leq j \leq i \leq N$）。 请输出路径上数字之和的最大值，输出为一行。 在 100 分中，有 50 分的数据满足 $N \leq 20$。

输出一行，表示路径上数字之和的最大值。

无。 由 ChatGPT 4.1 翻译