Preparing NOJ

数字梯形问题

1000ms 65536K

Description:

       给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m 个数字。从梯形的顶部的m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

规则1:从梯形的顶至底的m条路径互不相交。

规则2:从梯形的顶至底的m条路径仅在数字结点处相交。

规则3:从梯形的顶至底的m条路径允许在数字结点相交或交。

                                        

 对于给定的数字梯形,分别按照规则1,规则2,和规则3 计算出从梯形的

 顶至底的m条路径,使这m条路径经过的数字总和最大。

        

Input:

文件的第1 行中有2个正整数mnm,n<=20),分别表示数字梯形的第一行有m个数字,共有n 行。接下来的n 行是数字梯形中各行的数字。第1 行有m个数字,第2 行有m+1 个数字,…。

Output:

程序运行结束时,将按照规则1,规则2,和规则3 计算出的最大数字总和输出。每行一个最大总和。

Sample Input:

 2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

Sample Output:

66
75
77

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1363

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet