题目
传送门：QWQ
分析
求结尾0的数量QwQ。
10只能是$ 2 \times 5 $，我们预处理出每个数因子中2和5的数量。
我们接着dp出从左上到右下的经过的最少的2的数量和最少的5的数量。两者取min后就是答案。
特判数据中有0的情况，把他当做10处理。如果此时答案大于1，那么把答案更新成1。因为0只有1个0。
输出也有些小技巧
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
int a[maxn][maxn][], dp[maxn][maxn][];
void print(int x,int y,int k,int state){ if(x<= || y<=) return;
if(dp[x-][y][k]==dp[x][y][k]-a[x][y][k]) print(x-,y,k,);
else print(x,y-,k,); if(state==) return;
if(state==) putchar('R');
else putchar('D');
} int main(){
int n, posx, posy, flag=;
scanf("%d",&n);
for(int i=;i<=n;i++) {
for(int j=;j<=n;j++) {
int num; scanf("%d",&num);
if(!num) {
posx=i;posy=j; flag=;
a[i][j][]=a[i][j][]=; continue;
}
while(num%==) a[i][j][]++,num/=;
while(num%==) a[i][j][]++,num/=;
}
} memset(dp,,sizeof(dp));
dp[][][]=dp[][][] =;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int k=;k<;k++){
dp[i][j][k] = min (min(dp[i][j-][k],dp[i-][j][k]), dp[i][j][k]) + a[i][j][k];
}
}
}
int ans=min(dp[n][n][],dp[n][n][]);
if(flag && ans>){
printf("%d\n",);
for(int i=;i<posx;i++) putchar('D');
for(int i=;i<posy;i++) putchar('R');
for(int i=posx+;i<=n;i++) putchar('D');
for(int i=posy+;i<=n;i++) putchar('R');
return ;
}
printf("%d\n",ans);
if(dp[n][n][] > dp[n][n][]) print(n,n,,);
else print(n,n,,);
return ;
}