题意
n阶数字矩阵，从左上第一个数，到右下最后一个数，只能向右或向下走，经过的数字进行相乘，求最后结果尾数为0最少的路径
题解
若要相乘之后结果有0有两种情况
相乘的数中包含2和5，即要求经过2或5最少的路径经过0时，无论其他数为多少，最后都为1个0，因此要记录好0的位置，此处要特判 若相乘之后没有0，无疑是最好的
利用动态规划，通过题意写出转移方程：
D[r,c] = min(D[r-1,c],D[r,c-1]) + A[r][c]
f[x][y][z]表示在x行y列2和5的个数： f[x][y][0]：表示x行y列的2的个数 f[x][y][1]：表示x行y列的2的个数 g[x][y][z]表示在选择数字z时，x行y列处是向下还是向右，1是向下，0是向右
知识点
路径的输出，通过递归的方式进行回溯输出 若图为此，想从s[1][1]走到s[4][4]的路径是通过从s[4][4]倒推回s[1][1]的: s[4][4]为1，则输出D，即走到s[3][4] s[3][4]为1，则输出D，即走到s[2][4] s[2][4]为0，则输出R，即走到s[2][3] s[2][3]为0，则输出R，即走到s[2][2] s[2][2]为1，则输出D，即走到s[1][2] s[1][2]为0，则输出R，即走到s[1][1] s[1][1]为1，没啥用，直接return了
int s[5][5]={
0,0,0,0,0,
0,1,0,0,0,
0,0,1,0,0,
0,0,0,0,1,
0,0,0,0,1,
};
void func(int x, int y){
if(x==1 &&y==1) return;
if(s[x][y]){
func(x-1,y); putchar('D');
}
else{
func(x, y-1); putchar('R');
}
}
func(4,4); //RDRRDR
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#define inf 0x7fffffff
using namespace std;
int f[1001][1001][2],n,x,t;
char g[1001][1001][2];
void print(int x,int y){
if(x==1&&y==1)
return ;
if(g[x][y][t])
print(x-1,y),putchar('D');
else
print(x,y-1),putchar('R');
}
int main(void){
scanf("%d",&n);
memset(f,0,sizeof(f));
for(int i=2;i<=n;++i)
f[0][i][0]=f[0][i][1]=f[i][0][0]=f[i][0][1]=inf;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&t);
if(!t) x=i; //判断0在第x行
else{
while(t%2==0) ++f[i][j][0],t/=2;
while(t%5==0) ++f[i][j][1],t/=5;
}
for(int k=0;k<2;k++)
if((g[i][j][k]=f[i-1][j][k]<f[i][j-1][k]))
f[i][j][k]+=f[i-1][j][k];
else f[i][j][k]+=f[i][j-1][k];
}
}
t=f[n][n][1]<f[n][n][0];
if(x&&f[n][n][t]>1){ //有0的那行特判
puts("1");
for(int i=2;i<=x;i++) putchar('D');
for(int i=2;i<=n;i++) putchar('R');
for(int i=x+1;i<=n;i++) putchar('D');
puts("");
}
else
printf("%d\n",f[n][n][t]),print(n,n);
puts("");
}
