题目地址：Codeforces：Problem – 2B – Codeforces、洛谷：CF2B The least round way – 洛谷 | 计算机科学教育新生态

题目描述

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.

题意简述

给定一个$n \times n$的非负整数矩阵，要求你找出一条从左上角到右下角的路径，使得路径上的数字相乘得到的积的后缀0数量最少。

输入输出格式

输入格式：
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 10^9).

输出格式：
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

输入输出样例

输入样例#1：

3
1 2 3
4 5 6
7 8 9

输出样例#1：

0
DDRR

题解

考虑乘积的后缀0数量等于乘积中因数10的数量，则最小化乘积中质因子2和5的数量的思路很自然可以想出。答案即是最小化的2和5质因子数量中的较小值。
接下来考虑如何最小化答案。我们先用常规思路分别对质因子2和5的数量各自做一遍最小化，得到了两个答案，取其最小值即可。这个最小值一定可以取到，因为在取最小值时，最小化的那个质因子的数量一定比另外一个质因子小，这就保证了答案的正确性。
上面所说的“常规思路”是这样的一种动态规划思路：对于某一个点$(i, j)$，从左上角点$(1, 1)$到该处的路径上的最小质因子数量只能由左边的点$(i, j – 1)$和上面的点$(i – 1, j)$转移而来，即如果设$f(i, j)$是点$(i, j)$处的数字的某质因子数量，则上述状态的状态转移方程是
$$ dp(i, j) = f(i, j) + \min\{ dp(i – 1, j), dp(i, j – 1) \} $$

以为到这里就做完了？注意题目中有一个“非负整数”的坑，你还需要考虑路径中有0的情况。
如果路径中有0，会让路径的乘积变为0，即后缀0有1个。如果原本的最优路径的后缀0为0个，则原答案最优，否则应该经过这个数字为0的点。这个地方特例处理一下就可以了。
此外，注意处理一下边界情况无效状态不可转移即可。

算法总复杂度为$O(n^2)$。

代码

// Code by KSkun, 2019/6
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 1005;

int n, a[MAXN][MAXN], dp2[MAXN][MAXN], dp5[MAXN][MAXN];
char pre2[MAXN][MAXN], pre5[MAXN][MAXN], ans[MAXN << 1];
int atot = 0;
int zx = 0, zy = 0;

inline int calfac(int x, int f) {
    if(x == 0) return 0; // 注意x=0时进入死循环
    int cnt = 0;
    while(x % f == 0) {
        cnt++; x /= f;
    }
    return cnt;
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            a[i][j] = readint();
            if(a[i][j] == 0) {
                zx = i; zy = j;
            }
            dp2[i][j] = calfac(a[i][j], 2);
            dp5[i][j] = calfac(a[i][j], 5);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int r1 = dp2[i][j] + dp2[i - 1][j], r2 = dp2[i][j] + dp2[i][j - 1];
            if(i == 1) r1 = 1e9; // 边界情况无效状态设置为不可转移
            if(j == 1) r2 = 1e9;
            if(r1 < r2) {
                dp2[i][j] += dp2[i - 1][j]; 
                pre2[i][j] = 'D';
            } else {
                dp2[i][j] += dp2[i][j - 1]; 
                pre2[i][j] = 'R';
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int r1 = dp5[i][j] + dp5[i - 1][j], r2 = dp5[i][j] + dp5[i][j - 1];
            if(i == 1) r1 = 1e9; // 边界情况无效状态设置为不可转移
            if(j == 1) r2 = 1e9;
            if(r1 < r2) {
                dp5[i][j] += dp5[i - 1][j];
                pre5[i][j] = 'D';
            } else {
                dp5[i][j] += dp5[i][j - 1];
                pre5[i][j] = 'R';
            }
        }
    }
    int t;
    if(dp2[n][n] < dp5[n][n]) t = 2; else t = 5;
    if(zx && zy && (t == 2 ? dp2[n][n] : dp5[n][n]) > 1) {
        puts("1"); // 当包含0的路径是最优情况时的特殊处理
        for(int i = 1; i < zx; i++) putchar('D');
        for(int i = 1; i < zy; i++) putchar('R');
        for(int i = zx; i < n; i++) putchar('D');
        for(int i = zy; i < n; i++) putchar('R');
    } else {
        printf("%d\n", t == 2 ? dp2[n][n] : dp5[n][n]);
        int nx = n, ny = n;
        while(nx != 1 || ny != 1) {
            char op = t == 2 ? pre2[nx][ny] : pre5[nx][ny];
            ans[++atot] = op;
            if(op == 'D') nx--;
            else ny--;
        }
        for(int i = atot; i >= 1; i--) putchar(ans[i]);
    }
    return 0;
}