最小较小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;

}

文章结束给大家分享下程序员的一些笑话语录：

　一边用着越狱的ip，一边拜乔帮主的果粉自以为是果粉，其实在乔帮主的眼里是不折不扣的叛徒。

---------------------------------
原创文章 By
最小和较小
---------------------------------

巴特西

最小较小codeforces 2B The least round way

最新文章

热门文章