主要思路
这道题我一开始写的是纯暴力，然后卡在了第 6 个点上失败。在看题解之前就已经感觉到这应该跟数学有关系。我先大概地说明主要方法，在数字输入时用数组\(dp2[][]和dp5[][]\)来记录这个数字包含因子\(2\)的个数和因子\(5\)的个数，然后尾部\(0\)的个数是\(min\{numOf(2),numOf(5)\}\)。然后我们可以分开进行处理，可以先处理\(dp2[][]\)数组并记录路径数组\(f2[][]\)，之后处理\(dp2[][]和f5[][]\)。统计答案时只需要比较\(dp2[n][n]和dp5[n][n]\)，回溯\(f2[][]或f5[][]\)即可。
但是还有一种情况，那就是数字矩阵包括\(0\)的情况。我们可以考虑在预处理的时候记录下数字\(0\)的坐标，最后只要\(min\{dp2[n][n],dp5[n][n]\}>1\)，就证明\(0\)才是最优解。
代码
// CF2B.cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const int MX_N = 1010;
ll mat[MX_N][MX_N], dp2[MX_N][MX_N], dp5[MX_N][MX_N], pow2[25], pow5[25], n, zeroFlag, zeroX, zeroY;
char ans[MX_N << 1];
struct vec
{
ll x, y;
} f2[MX_N][MX_N], f5[MX_N][MX_N];
void preprocess()
{
for (int i = 0; i < 25; i++)
pow2[i] = 1 << i;
pow5[0] = 1;
for (int i = 1; i < 25; i++)
pow5[i] = pow5[i - 1] * 5;
}
void processDp()
{
// start to program dynamically;
for (int i = 2; i <= n; i++)
dp2[0][i] = dp2[i][0] = dp5[0][i] = dp5[i][0] = 2e9;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
ll vald = dp2[i - 1][j], valr = dp2[i][j - 1];
dp2[i][j] += min(vald, valr);
if (vald < valr)
f2[i][j] = vec{i - 1, j};
else
f2[i][j] = vec{i, j - 1};
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
ll vald = dp5[i - 1][j], valr = dp5[i][j - 1];
dp5[i][j] += min(vald, valr);
if (vald < valr)
f5[i][j] = vec{i - 1, j};
else
f5[i][j] = vec{i, j - 1};
}
}
int main()
{
scanf("%lld", &n);
preprocess();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%lld", &mat[i][j]);
if (mat[i][j] == 0)
{
zeroFlag = true, zeroX = i, zeroY = j;
continue;
}
int tmp = mat[i][j];
for (int k = 24; k >= 0; k--)
if (tmp % pow2[k] == 0)
dp2[i][j] += k, tmp /= pow2[k];
if (tmp % 2 == 0)
dp2[i][j]++;
tmp = mat[i][j];
for (int k = 24; k >= 0; k--)
if (tmp % pow5[k] == 0)
dp5[i][j] += k, tmp /= pow5[k];
if (tmp % 5 == 0)
dp2[i][j]++;
}
processDp();
// process the answer;
if (zeroFlag && min(dp2[n][n], dp5[n][n]) > 1)
{
puts("1");
for (int i = 2; i <= zeroX; i++)
putchar('D');
for (int j = 2; j <= zeroY; j++)
putchar('R');
for (int i = zeroX + 1; i <= n; i++)
putchar('D');
for (int j = zeroY + 1; j <= n; j++)
putchar('R');
return 0;
}
// secondary answer;
printf("%d\n", min(dp2[n][n], dp5[n][n]));
int cx = n, cy = n, tot = 0;
for (int counter = 1; counter <= 2 * n - 1; counter++)
{
int fx = f2[cx][cy].x, fy = f2[cx][cy].y;
if (dp2[n][n] > dp5[n][n])
fx = f5[cx][cy].x, fy = f5[cx][cy].y;
if (cx > fx)
ans[counter] = 'D';
else
ans[counter] = 'R';
cx = fx, cy = fy;
}
for (int i = 2 * n - 2; i >= 1; i--)
printf("%c", ans[i]);
return 0;
}
