首页 > 题解 > codeforce 2B The least round way

codeforce 2B The least round way

开坑CF DP

There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that

starts in the upper left cell of the matrix;
each following cell is to the right or down from the current cell;
the way ends in the bottom right cell.
Moreover, if we multiply together all the numbers along the way, the result should be the least “round”. In other words, it should end in the least possible number of zeros.

Input
The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

Output
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

Examples
input
3
1 2 3
4 5 6
7 8 9
output
0
DDRR

题意:

给定一个$n \times n$的一个表格,从$(1,1)$走到$(n,n)$,只能向右走或向下走。表的每个点有点权。每走到一个点就把点权乘起来。求一条路结果的后缀0最少。

题解

对于结果可以分解成

$$x=2^x+5^y+ \cdots $$

我们只需要考虑每个点权的2,5因子。我们预处理一下2,5因子。然后作两次DP,求出从左上到右下的2和5的个数最小值,答案就是两次结果的min。

但是还需要注意一种点权为0的情况。我们先把点权为0的点2,5因子个数都设成inf。然后看下dp出来的两个值那个是不是大于1。假如都大于1的话就走带0的路最优(只有一个后缀0)。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×