HBC213828模,gcd与exgcd,数论[网络流24题]数字梯形问题题解

淫家是湿人算法基础篇 2023-11-12 12:35:02 32 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

给定一个由n 行数字组成的数字梯形如下图所示，梯形的第一行有m 个数字，从梯形的顶部的m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径，规则1：从梯形的顶至底的m条路径互不相交，规则2：从梯形的顶至底的m条路径仅在数字结点处相交，规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交，对于给定的数字梯形，分别按照规则1，规则2，和规则3

给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m 个数字。从梯形的顶部的m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。规则1：从梯形的顶至底的m条路径互不相交。规则2：从梯形的顶至底的m条路径仅在数字结点处相交。规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。对于给定的数字梯形，分别按照规则1，规则2，和规则3 计算出从梯形的顶至底的m条路径，使这m条路径经过的数字总和最大。