思路
一眼看出考虑用动态规划。
分析，末尾 (0) 的个数与因数 (2,5) 的个数有关，那么我们输入的数组直接分别预处理成 (2) 的个数与 (5) 的个数就可以了。
其次，我们 (2,5) 的状态分别转移，取最终的最小值(因为如果没有 (5) ，取更多的 (2) 也没用)。
存储路径然后输出，也可以根据值的判断输出路径。
代码
需要控制的地方挺多，细心
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
const int MAXN = 1e3 + 10;
struct node {
int s_2 ,s_5;
node () {
s_2 = s_5 = 0x3f3f3f3f;
}
}dp[MAXN][MAXN];
int path[2][MAXN][MAXN];
int n;
pair <int ,int > g[MAXN][MAXN];
void f (int x ,int r1 ,int r2) {
int sum = 0 ,sum_ = 0;
while (x % 2 == 0)
x /= 2 ,sum ++;
while (x % 5 == 0)
x /= 5 ,sum_ ++;
g[r1][r2].first = sum ,g[r1][r2].second = sum_;
}
void print (int x ,int y ,int cmp ,char dir) {
if (x == 1 && y == 1) {
printf ("%c",dir);
return ;
}
if (path[cmp][x][y] == 0) print (x - 1 ,y ,cmp ,'D');
else print (x ,y - 1 ,cmp ,'R');
printf ("%c",dir);
}
int main () {
scanf ("%d",&n);
int x ,xx ,yy;
bool has_0 = false;
for (int q = 1;q <= n;++ q) {
for (int w = 1;w <= n;++ w) {
scanf ("%d",&x);
if (x == 0) {
has_0 = true ,xx = q ,yy = w;
g[q][w] = make_pair (0 ,0);
continue ;
}
f (x ,q ,w);
}
}
dp[1][0].s_2 = dp[0][1].s_2 = 0 ,dp[1][0].s_5 = dp[0][1].s_5 = 0;
for (int q = 1;q <= n;++ q) {
for (int w = 1;w <= n;++ w) {
if (dp[q - 1][w].s_2 < dp[q][w - 1].s_2)
dp[q][w].s_2 = dp[q - 1][w].s_2 + g[q][w].first ,path[0][q][w] = 0;
else dp[q][w].s_2 = dp[q][w - 1].s_2 + g[q][w].first ,path[0][q][w] = 1;
if (dp[q - 1][w].s_5 < dp[q][w - 1].s_5)
dp[q][w].s_5 = dp[q - 1][w].s_5 + g[q][w].second ,path[1][q][w] = 0;
else dp[q][w].s_5 = dp[q][w - 1].s_5 + g[q][w].second ,path[1][q][w] = 1;
}
}
if (has_0 && dp[n][n].s_2 > 1 && dp[n][n].s_5 > 1) {
printf ("1
");
for (int q = 1;q < xx;++ q) {
printf ("D");
}
for (int q = 1;q < n;++ q) {
printf ("R");
}
for (int q = xx;q < n;++ q) {
printf ("D");
}
return 0;
}
printf ("%d
",min (dp[n][n].s_2 ,dp[n][n].s_5));
if (dp[n][n].s_2 < dp[n][n].s_5) {
(path[0][n][n] ? print (n ,n - 1 ,0 ,'R') : print (n - 1 ,n ,0 ,'D'));
}
else {
(path[1][n][n] ? print (n ,n - 1 ,1 ,'R') : print (n - 1 ,n ,1 ,'D'));
}
return 0;
}