JikeStar 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答 语法周赛
登录 注册

2223: 菱形取数

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：18 解决：6

题目描述

小X同学最近碰到一个难题，需要你来帮他解决。
观察下边的数字菱形，写一个程序找到从最上端的点到最低端的点有一条路径，使路径经过的数字和最大。



例如上图中从13-11-67-45-43的路径产生了最大和179

输入

第一行为n，表示菱形最中间那行的数字数量。
第2到2n行，为这个数字菱形包含的所有数。

输出

包含一行，为数字菱形的最大和。

样例输入 复制 

3
13
11 5
13 67 42
12 45
43

样例输出 复制 

179

提示

30%的数据满足，n<=5。
100%的数据满足，n<=1000。
所有数字菱形内的数字都是不超过100的正整数。

来源/分类