codefore:2B. The least round way

中文

简介

存在由非负整数组成的正方形矩阵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;
}

 

上一篇:【AtCoder】AGC006


下一篇:第二次试验第一项