求從左上角到右下角所經過的數字之積末尾所含0最小的個數
最終的積可以看成A*2^x*5^y，0的個數就是x,y中較小的數，
所以只需要分別dp求出出現2，5的最小個數，再進行比較，選最小的一個
題目有個陷進：
就是給的數據可以為0，如果出現0的話，經過0這點的話結果為0，就是1個0，
如果不經過0的話，答案可能為0也可能>=1，所以只要求出不經過0出現最小0的個數跟1比較，
如果大於1的話，最小的就是經過0的答案，否則就不經過0.
[cpp]
#include<stdio.h>
#include<string.h>
#define N 1001
#define inf 0x3fffffff
int dp[N][N][2];
int num[N][N][2];//記錄每個數可分解2，5的個數
int dir[N][N][2];//記錄方向
void prif(int n,int x,int y)
{
if(x==y&&x==0)return;
if(dir[x][y][n]==0)
{
prif(n,x-1,y);
printf("D");
}
else if(dir[x][y][n]==1)
{
prif(n,x,y-1);
printf("R");
}
}
int main()
{
int n,i,j,k,a,b,ii,flag;
while(scanf("%d",&n)!=-1)
{
flag=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
dp[i][j][0]=dp[i][j][1]=inf;
scanf("%d",&a);
if(a==0){flag=1;ii=i;continue;}//記錄0所在行數
k=0;b=a;
while(b%2==0)
{
k++;
b/=2;
}
num[i][j][0]=k;//記錄a可分解2的個數
b=a;k=0;
while(b%5==0)
{
k++;
b/=5;
}
num[i][j][1]=k;//記錄a可分解5的個數
}
dp[0][0][0]=num[0][0][0];
dp[0][0][1]=num[0][0][1];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i-1>=0)
{
if(dp[i][j][0]>dp[i-1][j][0]+num[i][j][0])
{
dp[i][j][0]=dp[i-1][j][0]+num[i][j][0];
dir[i][j][0]=0;
}
if(dp[i][j][1]>dp[i-1][j][1]+num[i][j][1])
{
dp[i][j][1]=dp[i-1][j][1]+num[i][j][1];
dir[i][j][1]=0;
}
}
if(j-1>=0)
{
if(dp[i][j][0]>dp[i][j-1][0]+num[i][j][0])
{
dp[i][j][0]=dp[i][j-1][0]+num[i][j][0];
dir[i][j][0]=1;
}
if(dp[i][j][1]>dp[i][j-1][1]+num[i][j][1])
{
dp[i][j][1]=dp[i][j-1][1]+num[i][j][1];
dir[i][j][1]=1;
}
}
}
k=dp[n-1][n-1][0]>dp[n-1][n-1][1];
if(flag==1&&dp[n-1][n-1][k]>1)//如果有0，而且求得的最小值大於1，就選擇經過0的一條路徑
{
puts("1");
for(i=1;i<=ii;i++)
printf("D");
for(j=1;j<n;j++)
printf("R");
for(i=ii+1;i<n;i++)
printf("D");
}
else
{
printf("%d\n",dp[n-1][n-1][k]);
prif(k,n-1,n-1);
}
printf("\n");
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define N 1001
#define inf 0x3fffffff
int dp[N][N][2];
int num[N][N][2];//記錄每個數可分解2，5的個數
int dir[N][N][2];//記錄方向
void prif(int n,int x,int y)
{
if(x==y&&x==0)return;
if(dir[x][y][n]==0)
{
prif(n,x-1,y);
printf("D");
}
else if(dir[x][y][n]==1)
{
prif(n,x,y-1);
printf("R");
}
}
int main()
{
int n,i,j,k,a,b,ii,flag;
while(scanf("%d",&n)!=-1)
{
flag=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
dp[i][j][0]=dp[i][j][1]=inf;
scanf("%d",&a);
if(a==0){flag=1;ii=i;continue;}//記錄0所在行數
k=0;b=a;
while(b%2==0)
{
k++;
b/=2;
}
num[i][j][0]=k;//記錄a可分解2的個數
b=a;k=0;
while(b%5==0)
{
k++;
b/=5;
}
num[i][j][1]=k;//記錄a可分解5的個數
}
dp[0][0][0]=num[0][0][0];
dp[0][0][1]=num[0][0][1];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i-1>=0)
{
if(dp[i][j][0]>dp[i-1][j][0]+num[i][j][0])
{
dp[i][j][0]=dp[i-1][j][0]+num[i][j][0];
dir[i][j][0]=0;
}
if(dp[i][j][1]>dp[i-1][j][1]+num[i][j][1])
{
dp[i][j][1]=dp[i-1][j][1]+num[i][j][1];
dir[i][j][1]=0;
}
}
if(j-1>=0)
{
if(dp[i][j][0]>dp[i][j-1][0]+num[i][j][0])
{
dp[i][j][0]=dp[i][j-1][0]+num[i][j][0];
dir[i][j][0]=1;
}
if(dp[i][j][1]>dp[i][j-1][1]+num[i][j][1])
{
dp[i][j][1]=dp[i][j-1][1]+num[i][j][1];
dir[i][j][1]=1;
}
}
}
k=dp[n-1][n-1][0]>dp[n-1][n-1][1];
if(flag==1&&dp[n-1][n-1][k]>1)//如果有0，而且求得的最小值大於1，就選擇經過0的一條路徑
{
puts("1");
for(i=1;i<=ii;i++)
printf("D");
for(j=1;j<n;j++)
printf("R");
for(i=ii+1;i<n;i++)
printf("D");
}
else
{
printf("%d\n",dp[n-1][n-1][k]);
prif(k,n-1,n-1);
}
printf("\n");
}
return 0;
}
