UOJ Logo LFYZ Online Judge

LFYZOJ

#15. 【IOI1994】数塔问题

统计

问题描述

有形如图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大。

示意图

输入格式

n+1行:

第1行为一个数字n,代表塔的层数,接下来n行为每行的数字。 (1<=n<=99)

输出格式

max=ans,ans为一个整数,代表最大的路径数字总和。

样例一

input

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

output

max=30

数据范围与约定

时间限制: $1\mathrm{s}$

内存限制: $64\mathrm{MB}$

下载

样例数据下载