1080: 找金币

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:外部导入
提交:3 解决:3

题目描述

4、 找金币(100分)
最后,小明来到了一个叫做跳格找金币的地方,地上有N层格子,每个格子有数目不同的金币(小于200),格子是三角形分布,按每层递增一个,小明在每一层只能在一个格子上,也不能后退,也不能跨两格以上(无论是左还是右),也就是说,和我们经常玩的跳棋很类似,那么,小明要怎么办才能拿到最多的金币呢?
输入:两行,第一行是N(大于2,小于100),以下是N行,每行1-N个整数(每个格子的金币)
输出:一行(小明能得到的最多的金币数)
输入样例:
5
20
98 87
34 56 99
60 77 49 50
20 34 19 65 32
输出样例:
321

样例输入 复制

5
20
98 87
34 56 99
60 77 49 50
20 34 19 65 32

样例输出 复制

321