题面和翻译来自洛谷，链接

题面翻译

给定由非负整数组成的$n \times n$ 的正方形矩阵，你需要寻找一条路径：

以左上角为起点

每次只能向右或向下走

以右下角为终点
并且，如果我们把沿路遇到的数进行相乘，积应当是最小“round”，换句话说，应当以最小数目的0的结尾.

输入格式

第一行包含一个整数 n ($2 \leq n \leq 1000$)，n 为矩阵的规模，接下来的n行包含矩阵的元素（不超过10^9的非负整数）.

输出格式

第一行应包含最小尾0的个数，第二行打印出相应的路径（译注：D为下，R为右）

样例 #1

样例输入 #1

1
2
3
4
3
1 2 3
4 5 6
7 8 9

样例输出 #1

1
2
0
DDRR

题解

要使一个数末尾含有$0$，其质因子中必须同时有$2$和$5$，而其末尾$0$的数量取决于$2$和$5$当中最小的个数，也就是说每一对$2$和$5$在末尾产生一个$0$。

因此可以使用动态规划分别（不需要同时考虑）求出到终点能够积累的最少的$2$和$5$，在此过程中记录每一个点上最优决策移动过来的方向。由于数量最少的因子的路径上积累的另一个因子的数量必定大于等于终点的另一个因子的最小数量，只需顺着数量最少的因子的路径回查。

注意到如果矩阵中含$0$，则必定存在末尾含有$1$个$0$的路径，如果其为最优解特殊处理即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
// https://www.luogu.com.cn/problem/CF2B
const int N=1010,INF=0x3f3f3f3f;

int n;
int dp[N][N][2];
bool dir[N][N][2];

void print(int k){
    vector<bool> ans;
    int a=n,b=n;
    while(a!=1||b!=1){
        if(dir[a][b][k]==true){
            ans.push_back(true);
            a--;
        }
        else{
            ans.push_back(false);
            b--;
        }
    }
    for(int i=ans.size()-1;i>=0;i--)
        if(ans[i]==true) cout<<'D';
        else cout<<'R';
    cout<<endl;
}

int main(){
    fastIO
    cin>>n;
    int k;
    bool f=false;
    int p0;

    for(int i=0;i<=n;i++)
        dp[i][0][1]=dp[i][0][0]=dp[0][i][1]=dp[0][i][0]=INF; // 不可达状态

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>k;
            if(k==0){ // 标记含0的情况
                f=true;
                p0=i; // 记录0所在的行
                continue;
            }
            // 预处理该点可积累的因子数量
            int t=k;
            while(t%2==0){
                dp[i][j][0]++;
                t/=2;
            }
            t=k;
            while(t%5==0){
                dp[i][j][1]++;
                t/=5;
            }
        }
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<2;k++){
                if(dp[i-1][j][k]<dp[i][j-1][k]){
                    dp[i][j][k]+=dp[i-1][j][k];
                    dir[i][j][k]=true; // 由上方移动过来
                }
                else{
                    if(i==1&&j==1) continue; // 避免计算错误
                    dp[i][j][k]+=dp[i][j-1][k];
                    dir[i][j][k]=false;
                }
            }

    if(f&&min(dp[n][n][0],dp[n][n][1])>1){ // 特殊处理含0的情况
        cout<<1<<endl;
        for(int i=1;i<p0;i++) cout<<'D';
        for(int i=1;i<n;i++) cout<<'R';
        for(int i=1;i<=n-p0;i++) cout<<'D';
        cout<<endl;
    }
    else{
        cout<<min(dp[n][n][0],dp[n][n][1])<<endl;
        if(dp[n][n][0]<=dp[n][n][1]) k=0;
        else k=1;
        print(k);
    }

    return 0;
}