【题06】方格取数.doc

题题 6 6 方格取数方格取数 设有 n n 的方格图 我们将其中的某些方格中填入正整数 而其他的方格中则放入数字 如下图所示 见样例 向右 A12345678 100000000 2001300600 300007000 4000140000 5021000400 向 6001500000 下 7014000000 800000000 某人从图的左上角的 点出发 可以向下行走 也可以向右走 直到到达右下角的 点 在走过的 路上 它可以取走方格中的数 取走后的方格中将变为数字 此人从 点到 点共走两次 试找出 条这样的路径 使得取得的数之和最大 输入 输入的第一行为一个整数 表示 的方格图 接下来的每行右三个整数 前两个表示位置 第三个数为该位置上所放的数 一行单独的 表示输入结束 输出 只需输出一个整数 表示 条路径上取得的最大的和 分析 分析 我们对这道题并不陌生 如果求一条数和最大的路径 读者自然会想到动态程序设计方法 现在 的问题是 要找出这样的两条路径 是否也可以采用动态程序设计方法呢 回答是可以的 1 1 状态的设计 状态的设计 对于本题来说 状态的选定和存储对整个问题的处理起了决定性的作用 我们从 1 1 出发 每走一步作为一个阶段 则可以分成 2 n 1 个阶段 第一个阶段 两条路径从 1 1 出发 第二个阶段 两条路径可达 2 1 和 1 2 第三个阶段 两条路径可达的位置集合为 3 1 2 2 和 1 3 第 2 n 1 个阶段 两条路径汇聚 n n 在第 k 1 k 2 n 1 个阶段 两条路径的终端坐标 x1 y1 x2 y2 位于对应的右下对角线上 如下 图所示 如果我们将两条路径走第 i 步的所有可能位置定义为当前阶段的状态的话 面对的问题就是如何存 储状态了 方格取数问题的状态数目十分庞大 每一个位置是两维的 且又是求两条最佳路径 这就要 求在存储上必须做一定的优化后才有可能实现算法的程序化 主要的优化就是 舍弃一切不必要的存储 量 为此 我们取位置中的 x 坐标 x1 x2 作状态 其中 1 x1 k and x1 1 n and 1 x2 k and x2 1 n 直接由 X 坐标计算对应的 Y 坐标 Comment skz1 Page 2 y1 k 1 x1 and y1 1 n and y2 k 1 x2 and y2 1 n 2 2 状态转移方程 状态转移方程 设两条路径在 k 阶段的状态为 x1 x2 由 y1 k 1 x1 y1 1 n 得出第一条路径的坐标 为 x1 y1 由 y2 k 1 x2 y2 1 n 得出第二条路径的坐标为 x2 y2 假设在 k 1 阶段 两条路径的状态为 x1 x2 且 x1 x2 位于 x1 x2 状态的左邻或下邻位置 因此我们设两条路径 的延伸方向为 d1和 d2 di 0 表明第 i 条路径由 xi yi 向右延伸至 xi yi di 1 表明第 i 条路 径由 xi yi 向下延伸至 xi yi 1 i 2 显然 x1 x2 d1 d2 表明两条路径重合 同 时取走了 x1 y1 和 x1 y1 中的数 这种取法当然不可能得到最大数和的 分析两种可能 若 x1 x2 则两条路径会合于 x1状态 可取走 x1 y1 中的数 如下图 x1 x2 x1 x2 x2 x1 若 x1 x2 则在 k 阶段 第一条路径由 x1 状态延伸至 x1状态 第二条路径由 x2 状态延伸至 x2状 态 两条路径可分别取走 x1 y1 和 x2 y2 中的数 如下图 设 f k x1 x2 在第 k 阶段 两条路径分别行至 x1状态和 x2状态的最大数和 显然 k 1k 1 时 时 f 1f 1 1 1 1 01 0 k 2k 2 时 时 f kf k x x1 1 x x2 2 max f k 1 max f k 1 x x1 1 x x2 2 x x1 1 y y1 1 的数字的数字 x x1 1 x x2 2 f k 1 f k 1 x x1 1 x x2 2 x x1 1 y y1 1 的数字的数字 x x2 2 y y2 2 的数字的数字 x x1 1 x x2 2 1 k 2 n 11 k 2 n 1 x x1 1 可达可达 x x1 1的状态集合 的状态集合 x x2 2 可达可达 x x2 2的状态集合 的状态集合 x x1 1 x x2 2 d1 1 d d2 2 上述状态转移方程符合最优子结构和重叠子问题的特性 因此适用于动态程序设计方法求解 由于第 k 个阶段的状态转移方程仅与第 k 1 个阶段的状态发生联系 因此不妨设 f0 第 k 1 个阶段的状态转移方程 f1 第 k 个阶段的状态转移方程 初始时 f0 1 1 0 经过 2 n 1 个阶段后得出的 f0 n n 即为问题的解 3 多进程决策的动态程序设计 多进程决策的动态程序设计 由于方格取数问题是对两条路径进行最优化决策的 因此称这类动态程序设计为分阶段 多进程的 最优化决策过程 设 阶段 i 准备走第 i 步 1 i 2 n 1 状态 x1 x2 第 i 1 步的状态号 1 x1 x2 i 1 x1 x2 1 n 决策 d1 d2 第一条路径由 x1 状态出发沿 d1方向延伸 第二条路径由 x2 状态 出发沿 d2方 向延伸 可使得两条路径的数和最大 0 d1 d2 1 方向 0 表示右移 方向 1 表示下移 具体计算过程如下 fillchar f0 sizeof f0 0 行走前的状态转移方程初始化 f0 1 1 0 for i 2 to n n 1 do 阶段 准备走第 i 步 begin fillchar f1 sizeof f1 0 走第 i 步的状态转移方程初始化 for x1 1 to i 1 do 枚举两条路径在第 i 1 步时的状态 x1 和 x2 for x2 1 to i 1 do begin 计算 y1 和 y2 if x1 y1 和 x2 y2 在界内 then for d1 0 to 1 do 决策 计算两条路径的最佳延伸方向 for d2 0 to 1 do begin 第 1 条路径沿 d1方向延伸至 x1 y1 第 2 条路径沿 d2方向延伸至 x2 y2 if x1 y1 和 x2 y2 在界内 d1 d2 x1 x2 计算第 i 步的状态转移方程 the