1177 问题 D: 三角形

时间限制: 1s 内存限制: 128MB 提交: 7180 解决: 2946
题目描述

7 
3 8 

8 1 0 

2 7 4 4 

4 5 2 6 5 

(图一) 

图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径,使该路径经过的数字总和最大。 
每一步只能由当前位置向左下或右下。

输入

你的程序要能接受标准输入。第一行包含一个整数T,表示总的测试次数。 
对于每一种情况:第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。 
接下来的N行输入表示三角形的每一行的元素Ai,j,其中0 < Ai,j < 100。

输出

输出每次测试的最大值并且占一行。

样例输入
1 
5 
7 
3 8 
8 1 0  
2 7 4 4 
4 5 2 6 5
样例输出
30
提示
零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情

比赛公告

只是一次简单的比赛,督促大家准备蓝桥杯的比赛,做到查漏补缺,题目比较常规,适合新手。对于算法高手就是过加加。