同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2026_数字三角形

2022-5-16 18:18| 发布者: Hocassian| 查看: 66| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504252842100-Problem List-采集的数据-后羿采集器.html

Pro.ID

2026

Title

数字三角形

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2026

AC

276

Submit

837

Ratio

32.97%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

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

对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

输入

输入的第一行是数字三角形的行数n，1 ≤ n ≤ 600。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

输出

Description

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

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

对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

Input

输入的第一行是数字三角形的行数n，1 ≤ n ≤ 600。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

Output

输出一个数：计算出的最大值。

Sample Input

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

Sample Output

Author

John

样例输入