中文
简介
存在由非负整数组成的正方形矩阵n × n。你应该找到这样的一条路将所有数连起来，求积。
- 开始于左上方;
- 每个数从左边或者下边来链接下一个数;
- 结束于右下角。
此外，如果我们将所有数字相乘，积的结尾有最少的零。
左上角开始走，走到右下角，只能向右或向下走，将经过的数字相乘，求最后结果0最少的路径
思路：若要使相乘后尾部有0，有两种情况：1.其中包含2和5，记录2和5的个数分别为a,b要求尾部的0最少那么只要求经过的2或5最少的路径即可，也就是取a和b中较小值，
2.当经过0时，不论其他数为多少，最后都为1个0，如果1情况大于1，则优先选择2.
以上都粘贴过来的：
现在的问题是如何证明经过的2或者5最少即可。
利用归纳法的思想：
①10由2×5组成。
②n×10=n×2×5，那么对于含有m个2，n个5的情况，10的个数由min（m,n）决定。
代码剖析：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
//思路：统计数中含有2或者5的个数，含有尽量少的零一定含有尽量少的2与5，有兴趣的人可以尝试利用归纳法证明
int f[1001][1001][2],m,x,k;//f为三维数组，其中f[x][y][0]存储的是在点x,y为2的倍数的数的数量，其中f[x][y][1]储存的是在点x,y处为5的倍数的数，下见34,35行
char g[1001][1001][2];//用来记录路线，网下走为1，往右走为0
void fuck(int x,int y)
{
if(x==1&&y==1)//如果dp回到最开始的点，则结束
return;
if(g[x][y][k]){
fuck(x-1,y),putchar('D');//如果这个点的来源是上一个点往下走得来的
}
else{
fuck(x,y-1),putchar('R');//如果这个点的来源是上一点向又走得来的
}
}
int main()
{
int i;//开一个i计数
cin>>m;//读入矩阵的长度
memset(f,0,sizeof(f));//初始化矩阵，全部置零
for(i=2;i<=m;i++){
f[i][0][0]=f[0][i][0]=f[i][0][1]=f[0][i][1] = inf;//相当于设置墙壁，防止出界，建议画出图来更清晰。
}
for(int i=1;i<=m;i++)//遍历行号
{
for(int j=1;j<=m;j++){//遍历列号
scanf("%d",&k);//读入这个数
if(!k)//如果这这个数为零的话，记录这一行。如果都不为0的话，其实x应该为随机数的，因为没有进行过初始化，但是输出后x实际上为0，并没有进入矩阵之中
x = i;
else{
while(k%2==0) ++f[i][j][0],k/=2;//记录有几个2的倍数，比如8，由3个2组成，
while(k%5==0) ++f[i][j][1],k/=5;
}
for(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];//记录走到i，j这个点最少的步数
else
f[i][j][k] += f[i][j-1][k];
}
}
}
k = f[m][m][1] < f[m][m][0];//他这句话的意思是该路径中含有的2与5同时都小的时候才行
if(x&&f[m][m][k]>1){//这个讨论的是x不为零的时候，即如果最小的权值都大于1切有选择时候
cout<<"1\n";
for(i=2;i<=x;i++)
putchar('D');
for(i=2;i<=m;i++)
putchar('R');
for(i=x+1;i<=m;i++)
putchar('D');
}
else{
cout<<f[m][m][k]<<endl;
fuck(m,m);
}
return 0;
}