Problem #1823 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 1024 MB

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

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

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

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

Input

Output

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

172 人解决，277 人已尝试。

250 份提交通过，共有 920 份提交。

3.6 EMB 奖励。

创建: 17 年，5 月前.

修改: 7 年，3 月前.

最后提交: 1 月前.

DP

1823. 数塔II