跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0389. 三角形

  • ID: 395
  • 传统题
  • 1000ms
  • 128MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • 高校与竞赛共享题
  • 中文题面
  • 题目来源
  • 题面语言

三角形

题目描述

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

输入

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

输出

30

题目来源:吉首大学软件学院;FPS 共享题包,题包内第 69 题。保留原作者与原赛事署名。