最小較小codeforces 2B The least round way

查了好多資料，發現還是不全，幹脆自己整理吧，至少保證在我的做法正确的，以免誤導讀者，也是給自己做個記載吧！

    求從左上角到右下角所經過的數字之積末端所含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.

    每日一道理

那蝴蝶花依然花開花落，而我心中的蝴蝶早已化作雄鷹飛向了廣闊的藍天。

#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;
}