贡献了一列WA。。
数学很神奇啊
这个题的关键是怎么才能算尾0的个数 只能相乘 可以想一下所有一位数相乘 除0之外，只有2和5相乘才能得到0 当然那些本身带0的多位数 里面肯定含有多少尾0 就含有多少对2和5
这样就知道了 就是求2和5 的对数最少的 一条路 DP就不用说了 递推
注意有0的时候的计算 特殊处理一下
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
#define N 1010
#define INF 1e10
#define LL __int64
LL dp[N][N][];
int a[N][N],b[N][N];
int n;
char pa[N<<];
int init(int x,int k)
{
int num=;
while(x)
{
if(x%k==)
{
num++;
x/=k;
}
else break;
}
return num;
}
int main()
{
int i,j,y,o1,o2,f=;
scanf("%d",&n);
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
{
scanf("%d",&y);
if(y==)
{
o1 = i;
o2 = j;
f = ;
}
int o = init(y,);
a[i][j] = o;
o = init(y,);
b[i][j] = o;
}
for(i = ; i <= n; i++)
for(j = ; j <= n ; j++)
{
dp[i][j][] = INF;
dp[i][j][] = INF;
}
dp[][][] = a[][];
dp[][][] = b[][];
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
{
dp[i][j][] = min(dp[i][j][],min(dp[i-][j][],dp[i][j-][])+a[i][j]);
dp[i][j][] = min(dp[i][j][],min(dp[i-][j][],dp[i][j-][])+b[i][j]);
}
int g = ;
if(f&&min(dp[n][n][],dp[n][n][])>)
{
printf("1\n");
for(i = ; i < o2 ; i++)
printf("R");
for(i = ; i < o1 ; i++)
printf("D");
for(i = o2; i < n ; i++)
printf("R");
for(i = o1; i < n ; i++)
printf("D");
return ;
}
if(dp[n][n][]<dp[n][n][])
{
int i = n,j = n;
while()
{
if(i>&&dp[i][j][]==dp[i-][j][]+a[i][j])
{
i = i-;
pa[++g] = 'D';
}
else if(j>)
{
j = j-;
pa[++g] = 'R';
}
if(i==&&j==)
break;
}
}
else
{
int i = n,j = n;
while()
{
if(i>&&dp[i][j][]==dp[i-][j][]+b[i][j])
{
i = i-;
pa[++g] = 'D';
}
else if(j>)
{
j = j-;
pa[++g] = 'R';
}
if(i==&&j==)
break;
}
}
printf("%I64d\n",min(dp[n][n][],dp[n][n][]));
for(i = g ; i >= ; i--)
printf("%c",pa[i]);
puts("");
return ;
}