题解 CF2B 【The least round way】
耶耶小朋友
·
·
题解
个人感觉难度位于普及+/提高，不然我这个菜鸡咋做的出来。
做法:
这是一道动态规划题。
既然想要末尾最少个 0，那么组成末尾 0 的唯一办法只有 2\times5，所以末尾 0 的个数就等于因子 2 的个数与因子 5 的个数的最小值。
先分别获取该数因子 2 的个数和因子 5 的个数，预处理出 dp[i][j] 处是 dp[i-1][j] 大还是 dp[i][j-1] 大，最后再递归输出。
特判:
如果存在 0 且 [n,n] 位置 2、5 较小的个数大于一的话，从起点一直下到有 0 的那一行，直接走完那一行后一直往下到达终点。
提示:
$dp[i][j][1]$ 表示走到当前 $[i,j]$ 位置的因子 $5$ 的个数。
$big[i][j]$ 表示递归输出时往上好还是往左好。
$x$ 为记录有 $0$ 的那一行。
## Code:
``` C++
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 1000100101;
int dp[N][N][2];
int x = -1,k;
bool big[N][N][2];
void out(int x,int y) {
if(x == 1 && y == 1) {
return;
}
if(big[x][y][k] == false){
out(x,y - 1);
printf("R");
} else {
out(x - 1,y);
printf("D");
}
}
int main() {
int n;
scanf("%d",&n);
int i,j;
for(i = 2;i <= n;i++){
dp[i][0][0] = dp[0][i][0] = INF;
dp[i][0][1] = dp[0][i][1] = INF;
}
for(i = 1;i <= n;i++) {
for(j = 1;j <= n;j++){
scanf("%d",&k);
if(k == 0) {
x = i;
} else {
while(k % 2 == 0) {
dp[i][j][0]++;
k /= 2;
}
while(k % 5 == 0) {
dp[i][j][1]++;
k /= 5;
}
}
for(int x = 0;x < 2;x++){
if(dp[i-1][j][x] < dp[i][j-1][x]) {
dp[i][j][x] += dp[i-1][j][x];
big[i][j][x] = true;
} else {
dp[i][j][x] += dp[i][j-1][x];
big[i][j][x] = false;
}
}
}
}
k = 0;
if (dp[n][n][0] > dp[n][n][1]) {
k = 1;
}
if(x != -1 && dp[n][n][k] > 1){
puts("1");
for(i = 1;i < x;i++) {
printf("D");
}
for(i = 1;i < n;i++) {
printf("R");
}
for(i = x;i < n;i++) {
printf("D");
}
return 0;
}
printf("%d\n",dp[n][n][k]);
out(n,n);
return 0;
}
```