题目名称	730. [USACO 1.5] 数字金字塔
输入输出	`numtri.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	9
题目来源	祝一帆于2012-04-05加入修改该题
开放分组	全部用户
提交状态
分类标签	USACO 动态规划递推
	分享题解

通过：295，提交：538，通过率：54.83%
王伟	100	0.005 s	0.34 MiB	C++
张天翔	100	0.006 s	0.32 MiB	C++
hx	100	0.007 s	0.34 MiB	C++
野	100	0.008 s	0.04 MiB	C++
李昊泽	100	0.012 s	1.07 MiB	C++
Marvolo	100	0.012 s	2.08 MiB	Pascal
Pine	100	0.020 s	0.89 MiB	C++
hx	100	0.021 s	0.34 MiB	C++
郭思涵	100	0.021 s	1.13 MiB	C++
代金永	100	0.022 s	1.13 MiB	C++

关于数字金字塔的近10条评论(全部评论)
不用滚动数组吧？1000*1000评测姬可以呀夜莺 2020-02-23 20:03 22楼
评测机神了，2000*2000没有任何问题增强型图元文件 2018-08-11 22:35 21楼
这水题居然跪了两次。。 _WA自动机 2017-07-20 09:11 20楼
AntiLeaf 2017-05-25 15:46 19楼
kZime 2017-01-25 14:01 18楼
hh 蓝T-shirt 2016-10-25 20:03 17楼
递推 zyf 2016-10-25 19:33 16楼
写一发随机化试水竟然过了5个点 kxxy 2016-10-10 08:31 15楼
跟ioi1994数塔有区别么... Hzoi_ 2016-02-16 20:55 14楼
破数据太狗了 Dissolute丶Tokgo 2015-10-22 00:37 13楼

730. [USACO 1.5] 数字金字塔

★ 输入文件：numtri.in 输出文件：numtri.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大

【输入格式】

第一个行包含 R(1<= R<=1000) ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

所有的被供应的整数是非负的且不大于100。

【输出格式】

单独的一行,包含那个可能得到的最大的和。

【输入样例】

【输出样例】