问题1611--数字直角三角形的最大和路径

1611: 数字直角三角形的最大和路径

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

解决: 13提交: 24统计

题目描述

给你一个由数字构成的数字直角三角形，从最上方的数字开始，只能向正下或右下走，直到最后一行为止，请编程求解最大路径和和其对应的路径数字序列。

输入

第一行是N(N<=100)，表示数字三角形中数字的行数。接下来N行对应数字三角形，数字三角形中的数字大小不超过1000。

输出

第一行输出满足题意的最大路径和。第二行是最大路径和对应路径上的数字序列。

样例输入 Copy 

3
1
3 1
4 5 6

样例输出 Copy 

9
1 3 5

来源/分类

动态规划 
提交