线性规划与网络流24题----16数字梯形问题

算法实现题8-16数字梯形问题«问题描述：给定一个由n行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。规则1：从梯形的顶至底的m条路径互不相交。规则2：从梯形的顶至底的m条路径仅在数字结点处相交。规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。233459109111101111101211«编程任务：对于给定的数字梯形，分别按照规则1，规则2，和规则3计算出从梯形的顶至底的m条路径，使这m条路径经过的数字总和最大。«数据输入：由文件input.txt提供输入数据。文件的第1行中有2个正整数m和n（m,n=20），分别表示数字梯形的第一行有m个数字，共有n行。接下来的n行是数字梯形中各行的数字。第1行有m个数字，第2行有m+1个数字，…。«结果输出:程序运行结束时，将按照规则1，规则2，和规则3计算出的最大数字总和输出到文件output.txt中。每行一个最大总和。输入文件示例输出文件示例input.txtoutput.txt25233459109111101111101211667577