传送门
Solution
每个 10 都是由一对 2、5 相乘而得。设 Fi,j,0 为点 (1,1) 到 (i,j) 路上最少 2 的数量，Fi,j,1 为最少 5 的数量。答案即为 ans=min{Fn,n,0,Fn,n,1}。
注意若 ans>1 且方阵中有 0，则特判将答案改为经过这个 0 的路径，ans 改为 1。
dp 求出 F，在 dp 过程中记录当前点由上或下转移而来，最后通过递归输出路径。
Code
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1005;
ll n, a[N][N], f[N][N][2], flg, ans = 1e16, zx, zy;
char c[N][N][2];
void print(ll x, ll y, ll k)
{
if (x == y && x == 1)
return;
if (c[x][y][k] == 'R')
print(x, y - 1, k);
else
print(x - 1, y, k);
putchar(c[x][y][k]);
}
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%lld", &a[i][j]);
if (a[i][j] == 0) {
f[i][j][0] = f[i][j][1] = -1;
zx = i; zy = j;
flg = 1;
continue;
}
ll num = a[i][j];
while (num % 2 == 0) {
f[i][j][0]++;
num >>= 1;
}
while (num % 5 == 0) {
f[i][j][1]++;
num /= 5;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j && i == 1 || f[i][j][0] == f[i][j][1] && f[i][j][0] == -1) continue;
if (i > 1 && f[i - 1][j][0] == -1 || i == 1) {
if (j > 1 && f[i][j - 1][0] == -1 || j == 1) {
f[i][j][0] = f[i][j][1] = -1;
continue;
} else if (j > 1) {
f[i][j][0] += f[i][j - 1][0];
f[i][j][1] += f[i][j - 1][1];
c[i][j][0] = c[i][j][1] = 'R';
}
continue;
}
if (j == 1 || j > 1 && f[i][j - 1][0] == -1) {
if (i == 1 || i > 1 && f[i - 1][j][0] == -1) {
f[i][j][0] = f[i][j][1] = -1;
continue;
} else if (i > 1) {
f[i][j][0] += f[i - 1][j][0];
f[i][j][1] += f[i - 1][j][1];
c[i][j][0] = c[i][j][1] = 'D';
}
continue;
}
if (f[i - 1][j][0] >= f[i][j - 1][0]) {
f[i][j][0] += f[i][j - 1][0];
c[i][j][0] = 'R';
} else {
f[i][j][0] += f[i - 1][j][0];
c[i][j][0] = 'D';
}
if (f[i - 1][j][1] >= f[i][j - 1][1]) {
f[i][j][1] += f[i][j - 1][1];
c[i][j][1] = 'R';
} else {
f[i][j][1] += f[i - 1][j][1];
c[i][j][1] = 'D';
}
}
}
if (f[n][n][0] != -1)
ans = min(ans, f[n][n][0]);
if (f[n][n][1] != -1)
ans = min(ans, f[n][n][1]);
if (ans > 1 && flg) {
printf("1\n");
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 if (ans == 1e16) {
printf("1\n");
for (int i = 1; i < n; i++)
putchar('D');
for (int i = 1; i < n; i++)
putchar('R');
} else {
printf("%lld\n", ans);
if (f[n][n][0] <= f[n][n][1])
print(n, n, 0);
else
print(n, n, 1);
}
return 0;
}
|