1823. 数塔II

单点时限: 2.0 sec

内存限制: 1024 MB

有一个由正整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数,如下图所示。

   1
  3 2
 4 10 1
4 3  2 20

从第一行的数开始,除了某一次可以走到下一行的任意位置外,每次都只能左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来。如何走,使得这个和尽量大?

输入格式

输入数据首先包括一个整数 $C$,表示测试实例的个数,每个测试实例的第一行是一个整数 $N$ ($1 \le N \le 500$),表示数塔的高度,接下来用 $N$ 行数字表示数塔,其中第 $i$ 行有个 $i$ 个整数,且所有的整数均在区间 $[0,99]$ 内。

输出格式

对于每个测试实例,输出可能得到的最大和。

样例

Input
1
4
1
3 2
4 10 1
4 3 2 20
Output
34

提示

路径:1->3->10->20

143 人解决,244 人已尝试。

212 份提交通过,共有 768 份提交。

3.9 EMB 奖励。

创建: 12 年,11 月前.

修改: 2 年,10 月前.

最后提交: 1 周,3 天前.

来源: partychen

题目标签
DP