2256: 数塔问题II

考虑在下面被显示的数字金字塔。

写一个程序来计算从最高点开始，并且在底部任意处结束的路径经过数字的和的最大值。每一步可以走到正 下方的点也可以到达右下方的点。

7

3    8

8    1    0

2    7    4    4

4    5    2    6    5

在上面的样例中,从 7  →   3   →  8  →  7  →  5  的路径产生了最大和为 30。

第 1  个行包含 N(1 ≤ N  ≤ 100)  ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于 100。

第 1  行输出一个整数，即那个可能得到的最大的和。

第 2  行输出一条可行路线，路线格式详见样例输出。如有多种可行路线，任意输出一种即可。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30
(1,1)->(2,1)->(3,1)->(4,2)->(5,2)