| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2367 人关注过本帖
标题:有趣的三角形最大和问题(ACM题)
取消只看楼主 加入收藏
心剑菩提
Rank: 1
等 级:新手上路
帖 子:249
专家分:0
注 册:2007-5-17
收藏
 问题点数:0 回复次数:0 
有趣的三角形最大和问题(ACM题)

三角形最大和问题

Time Limit:1000MS Memory Limit:65536K
Total Submit:79 Accepted:22

Description

现在经常有一些数学问题困扰着小明。有如下一个三角形,

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

小明想求出从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。现在想请你编一个程序实现这个问题。
说明:
(1)每一步可沿左斜线向下或右斜线向下;
(2)1<三角形行数≤100;
(3)三角形中的数字为0,1,...,99。

Input

输入有多个实例。每个测试用例的第一行是三角形的行数n,接下来是n行数字,每行数字的个数由1开始,依次加1。

Output

输出每个测试用例的最大和(整数),每行1个。

Sample Input


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

Sample Output


30

Source

搜索更多相关主题的帖子: 三角形最大 ACM 数学 Limit 数字 
2007-06-12 14:20
快速回复:有趣的三角形最大和问题(ACM题)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015724 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved