题目大意：
一个n*n的矩阵，从矩阵的左上角开始，每次移动到下面或者右面，移动到右下角结束。 要求走的路径上的所有数字乘起来，乘积得到的值后面的0最少。
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;
typedef long long LL;
const LL INF = 0xffffff;
const int maxn = ;
const LL MOD = 1e9+;
struct node
{
int num2, num5;
} dp2[maxn][maxn], dp5[maxn][maxn], a[maxn][maxn];
int K[maxn][maxn], n; bool HaveZero(int& x,int& y)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(K[i][j] == )
{
x = i;
y = j;
return true;
}
}
}
return false;
} void PutPath5(int x,int y)
{
if(x == && y == )
return;
if(dp5[x][y].num2 == dp5[x-][y].num2 + a[x][y].num2 && dp5[x][y].num5 == dp5[x-][y].num5 + a[x][y].num5)
{
PutPath5(x-, y);
printf("D");
}
else
{
PutPath5(x, y-);
printf("R"); }
} void PutPath2(int x,int y)
{
if(x == && y == )
return;
if( dp2[x][y].num2 == dp2[x-][y].num2 + a[x][y].num2 && dp2[x][y].num5 == dp2[x-][y].num5 + a[x][y].num5)
{
PutPath2(x-, y);
printf("D");
}
else
{
PutPath2(x, y-);
printf("R");
}
} void PutPath()
{
int x, y;
int ans = min( min(dp2[n][n].num2,dp2[n][n].num5) , min(dp5[n][n].num2,dp5[n][n].num5) );
if( HaveZero(x,y) && ans > )
{
printf("1\n");
for(int i=; i<=x; i++)
printf("D");
for(int i=; i<=y; i++)
printf("R");
for(int i=x+; i<=n; i++)
printf("D");
for(int i=y+; i<=n; i++)
printf("R");
return ;
}
if( min(dp2[n][n].num2,dp2[n][n].num5) < min(dp5[n][n].num2,dp5[n][n].num5) )
{
printf("%d\n", min(dp2[n][n].num2,dp2[n][n].num5));
PutPath2(n, n);
}
else
{
printf("%d\n", min(dp5[n][n].num2,dp5[n][n].num5));
PutPath5(n, n);
} } void Process(int i,int j,int p)
{
int k = p;
while(k)
{
if(k% == )
a[i][j].num2 ++;
else
break;
k /= ;
}
k = p;
while(k)
{
if(k% == )
a[i][j].num5 ++;
else
break;
k /= ;
}
}
int main()
{
cin >> n;
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
scanf("%d", &K[i][j]);
Process(i, j, K[i][j]);
} for(int i=; i<=n; i++)
{
dp2[i][].num5 = dp2[i][].num2 = dp2[][i].num2 = dp2[][i].num5 = INF;
dp5[i][].num5 = dp5[i][].num2 = dp5[][i].num2 = dp5[][i].num5 = INF;
a[][i].num2 = a[][i].num5 = a[i][].num2 = a[i][].num5 = INF;
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
dp2[i][j] = a[i][j];
dp5[i][j] = a[i][j];
if(dp2[i-][j].num2 > dp2[i][j-].num2 && j->)
{
dp2[i][j].num2 += dp2[i][j-].num2 ;
dp2[i][j].num5 += dp2[i][j-].num5 ;
}
else if(i- > )
{
dp2[i][j].num2 += dp2[i-][j].num2;
dp2[i][j].num5 += dp2[i-][j].num5;
} if(dp5[i-][j].num5 > dp5[i][j-].num5 && j->)
{
dp5[i][j].num2 += dp5[i][j-].num2;
dp5[i][j].num5 += dp5[i][j-].num5;
}
else if(i- > )
{
dp5[i][j].num2 += dp5[i-][j].num2 ;
dp5[i][j].num5 += dp5[i-][j].num5 ;
}
} PutPath();
printf("\n");
return ;
}