做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2092. -- 宝典2第二章数字三角形

2092: 宝典2第二章数字三角形

时间限制: 1 Sec  内存限制: 128 MB
提交: 53  解决: 26
[上一题][提交][讨论版][状态][下一题]

题目描述

【题目描述】数字三角形(tower.cpp/c/pas)

对于大多数人来说,“我们是这么的正常,因此也就这么的平庸。”而天才总是与众不同的,所以当邪狼问修罗王:“老大,你蹲在那儿一动不动看了有半个小时了,蚂蚁有那么好看吗?”

修罗王是这样回答的:“我在思索人生的意义,你看这蚂蚁的面前有无数的道路选择,但它不知道选择哪条路可以到达目标,也不知道哪条路上有更多的食物,更不知道现在选择的道路对它以后的影响……”

如图所示,有一个层数为n(n≤1000)的数字三角形。现有一只蚂蚁从顶层开始向下走,每走下一级时,可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。

【输入格式】

第一个整数为n,以下n行为各层的数字。

【输出格式】

一个整数,即最大值,保证不超过整型的最大范围。

【输入样例】

5

1

6 3

8 2 6

2 1 6 5

3 2 4 7 6

【输出样例】

23

【样例说明】

最大值=1+3+6+6+7=23

标签

[上一题][提交][讨论版][状态][下一题]