最少的末尾零路径 题解

思路

一个非零整数末尾零的数量等于其质因子 2 与质因子 5 的指数较小值。路径乘积的指数等于路径上各数指数之和。因此分别求出“因子 2 总数最少的路径”和“因子 5 总数最少的路径”，两者中较优者就是不经过零时的最优解。

零需要单独处理。计算 DP 时把零的两种因子数都设为极大值；如果普通路径答案大于 1 且矩阵中存在零，就构造一条经过零的路径，其乘积为零，按题目约定答案为 1。

做法

子任务 1 枚举所有由 D、R 组成的合法路径，直接累计因子数并检查零。

子任务 2 以因子 2 总量作为额外状态：在每个格子、每个可能的因子 2 总量下，记录因子 5 总量的最小值。这保留了所有可能的二者权衡，再在终点取 $\min(c_2,c_5)$ 最小的状态。

完整做法对因子 2 和因子 5 分别运行一次二维最短路式 DP。每个格子只从上方或左方转移，并记录前驱方向以恢复路径。

复杂度

子任务 1 的时间复杂度为 $O(\binom{2n-2}{n-1}n)$。子任务 2 的时间复杂度为 $O(n^3\log A)$，空间复杂度为 $O(n^3\log A)$。完整做法的时间复杂度和空间复杂度均为 $O(n^2)$。