【學習筆記】CF2B The least round way 題解

題目傳送門

正解

顯然，末尾 0 的個數僅和路徑中各數 2 和 5 的因子的最小值有關，因為隻有 2 和 5 搭配才能産生 0 。

當然，如果走了一個 0 ，那麼無論如何，都有且僅有一個 0 ！

是以，分别對 2 和 5 做一遍 DP，取最小值即可。

當然，如果有 0 ，答案最大肯定就隻能是 1 辣！

那麼，怎麼輸出路徑呢？

比較簡單，如果選擇走 0 的話，直接按照如下路徑走即可：

反之，在 DP 的時候記錄一下前驅，然後倒推并輸出即可。