TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1951
  • 题目
  • P1951【线性规划与网络流24题 16】数字梯形
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。
    规则1:从梯形的顶至底的m条路径互不相交。
    规则2:从梯形的顶至底的m条路径仅在数字结点处相交。
    规则3:从梯形的顶至底的m条路径允许在数字结点相交或边相交。
    以上三种规则的m条路都必须分别从第一行的m个位置出发,不重复也不遗漏;但第2,3种规则找出的路径可以在终点处重合。


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



    编程任务:
    对于给定的数字梯形,分别按照规则1,规则2,和规则3 计算出从梯形的顶至底的m条路径,使这m条路径经过的数字总和最大。

    输入格式

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

    输出格式

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

    样例输入

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

    样例输出

    66
    75
    77


    来源  感谢 Wo_ai_WangYuan 放上数据