codeforces 2B The least round way(DP+数学)

The least round way

题目链接:http://codeforces.com/contest/2/problem/B

　　　　——每天在线，欢迎留言谈论。PS.本题有什么想法、建议、疑问欢迎留言！！

题目大意：

①第一行给你一个n，表示接下来将给你一个n阶方阵的数据

②要求你从左上方出发到右下方，路径上所有数字乘积的末尾0的个数最少

③输出最少0的个数，并输出路径

PS：①每次只能向右或向走 ②D表示向下走，R表示向右 ③0乘任何数的结果末尾都是一个0；

知识点：

①多个数字相乘，末尾0个个数为：每个乘数分解质因数后 min(2的个数，5的个数)；

②基本的DP(动态规划)- 本题dp出2、5 个数的最小值。

思路：

①末尾0个个数只跟线路上2、5的个数有关，所以读入数据时只要保存 2、5的个数即可

②通过dp，分别找出 2个数最小的路和5个数最小的路。

③那么结果有情况：下面用num2、num5表示 2、5最小的个数

④由于0比较特殊所以需要考虑 (①把他当作10②记入第一个0的位子)(自己想为什么可以喽。。哈哈)

Ⅰ. num2、num5 当中全为0或其中一个为0

　　代表有某条路乘级末尾无0；直接输出。

Ⅱ . 如果输入数据中有0，那么0乘任何数末尾都是一个0，直接输出带0的一条路即可

Ⅲ . 其他无0情况输出 min(num2,num5) 那条路就可以了！

感想：

这题的难点在于对多个数相乘末尾0的个数性质的了解和对有0的处理。

o.o 这个题要考虑的细节确实有点多，需要慢慢考虑。

o.o 输出的部分我既然写了40行代码。。。

PS.本题有什么想法、建议、疑问欢迎留言！！

AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 const int MAXN=1005;
  7 const int inf=0x3f3f3f3f;
  8 struct node
  9 {
 10     int times[2];
 11     node(int a=0,int b=0){times[0]=a;times[1]=b;}
 12 };
 13 //----这里有几个全局变量↓
 14 node matrix[MAXN][MAXN];int n;//记录每个点的质因子2 5的个数
 15 bool isfind[MAXN][MAXN],ishavezero=false;//dp 时 记忆化搜索用
 16 int zeroy=0;
 17 //----这里有几个全局变量↑
 18 int get_num(int num,int y)
 19 {//获取数字num 质因子中 y 的个数
 20     int temp=0;
 21     while(num!=0&&num%y==0)
 22     {
 23         temp++;
 24         num/=y;
 25     }
 26     return temp;
 27 }
 28 int dp(int y,int i=1,int j=1)//动态规划：通过记忆搜索的方法
 29 {//y用来表示dp的是2还是5  y=0为2  y=1为5  ps.node结构体中int times[2];节省重复代码
 30     if(isfind[i][j])//是否已搜索过
 31         return matrix[i][j].times[y];
 32     isfind[i][j]=true;
 33     if(i==n&&j==n)//开始边界处理
 34         {return matrix[i][j].times[y];}
 35     else if(i==n)
 36         return matrix[i][j].times[y]=matrix[i][j].times[y]+dp(y,i,j+1);
 37     else if(j==n)
 38         return matrix[i][j].times[y]=matrix[i][j].times[y]+dp(y,i+1,j);
 39     //中间一般情况
 40     return matrix[i][j].times[y]=matrix[i][j].times[y]+min(dp(y,i+1,j),dp(y,i,j+1));
 41 }
 42 void putout()
 43 {//开始输出答案  ps.输出答案 写了40行的代码。。。。我也是lj
 44     int y=0;
 45     if(matrix[1][1].times[0]>matrix[1][1].times[1])
 46         y=1;
 47     if(ishavezero&&matrix[1][1].times[y]>0)
 48     {
 49         cout<<"1"<<endl;
 50         for(int i=1;i<n;)
 51         {
 52             if(i==zeroy)
 53             {
 54                 for(int j=1;j<n;j++)
 55                     cout<<"D";
 56             }
 57             cout<<"R";i++;
 58         }
 59         return ;
 60     }
 61         cout<<matrix[1][1].times[y]<<endl;
 62         for(int i=1;i<=n;)
 63             for(int j=1;j<=n;)
 64         {
 65             if(j==n&&i==n)return ;
 66             else if(j==n)
 67             {for(int t=i;t<n;t++)
 68                     cout<<"D";return ;
 69             }
 70             else if(i==n)
 71             {for(int t=j;t<n;t++)
 72                     cout<<"R";return ;
 73             }
 74             if(matrix[i+1][j].times[y]<=matrix[i][j+1].times[y])
 75             {
 76                 cout<<"D";
 77                 i++;
 78             }
 79             else
 80             {cout<<"R";j++;}
 81         }
 82 cout<<endl;
 83 }
 84 int main()
 85 {
 86     int temp;//接受输入的数
 87     cin>>n;
 88     for(int i=1;i<=n;i++)
 89         for(int j=1;j<=n;j++)
 90     {
 91         cin>>temp;
 92         if(!temp)
 93             {temp=10;if(!ishavezero){ishavezero=true;zeroy=j;}}
 94         matrix[i][j]=node(get_num(temp,2),get_num(temp,5));
 95     }
 96     memset(isfind,0,sizeof(isfind));//out();
 97     dp(0);
 98     memset(isfind,0,sizeof(isfind));
 99     dp(1);//out();
100     putout();
101     return 0;
102 }

2017-05-12 13:21:50