题解

思路

一个乘积的末尾零数等于其质因子 $2$ 和 $5$ 的总指数较小者。记第 $i$ 个数的两个指数为 $p_i,q_i$，问题变为选择 $k$ 对，使 $\min(\sum p_i,\sum q_i)$ 最大。

做法

设 $dp[j][s]$ 为选了 $j$ 个数、因子 $5$ 总数为 $s$ 时，因子 $2$ 总数的最大值。逐个数倒序更新。答案为 $\max_s\min(s,dp[k][s])$。由于 $a_i\le10^{18}$，每个数的因子 $5$ 不超过 $25$，总状态范围至多 $5000$。

小规模枚举全部子集。若所有数都是 $10$ 的幂，每个数的两个指数相等，直接选择指数最大的 $k$ 个。独立 Oracle 使用复制上一层的滚动表转移，与标程的原地倒序更新互证。

正确性证明

状态精确记录选择数量和因子 $5$ 总数，并在相同状态下保留最大的因子 $2$ 总数；较小值不可能在任何后续选择中反超，因此可安全舍弃。每个数的选与不选均被转移覆盖，归纳后 $dp[k]$ 包含所有合法选择的最优代表。枚举 $s$ 取两类指数较小者的最大值即为答案。

复杂度

时间复杂度 $O(nkS)$，空间复杂度 $O(kS)$，其中 $S\le5000$。