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代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=;
const int inf=0x3f3f3f3f;
struct node
{
int times[];
node(int a=,int b=){times[]=a;times[]=b;}
};
//----这里有几个全局变量↓
node matrix[MAXN][MAXN];int n;//记录每个点的质因子2 5的个数
bool isfind[MAXN][MAXN],ishavezero=false;//dp 时 记忆化搜索用
int zeroy=;
//----这里有几个全局变量↑
int get_num(int num,int y)
{//获取数字num 质因子中 y 的个数
int temp=;
while(num!=&&num%y==)
{
temp++;
num/=y;
}
return temp;
}
int dp(int y,int i=,int j=)//动态规划：通过记忆搜索的方法
{//y用来表示dp的是2还是5 y=0为2 y=1为5 ps.node结构体中int times[2];节省重复代码
if(isfind[i][j])//是否已搜索过
return matrix[i][j].times[y];
isfind[i][j]=true;
if(i==n&&j==n)//开始边界处理
{return matrix[i][j].times[y];}
else if(i==n)
return matrix[i][j].times[y]=matrix[i][j].times[y]+dp(y,i,j+);
else if(j==n)
return matrix[i][j].times[y]=matrix[i][j].times[y]+dp(y,i+,j);
//中间一般情况
return matrix[i][j].times[y]=matrix[i][j].times[y]+min(dp(y,i+,j),dp(y,i,j+));
}
void putout()
{//开始输出答案 ps.输出答案 写了40行的代码。。。。我也是lj
int y=;
if(matrix[][].times[]>matrix[][].times[])
y=;
if(ishavezero&&matrix[][].times[y]>)
{
cout<<""<<endl;
for(int i=;i<n;)
{
if(i==zeroy)
{
for(int j=;j<n;j++)
cout<<"D";
}
cout<<"R";i++;
}
return ;
}
cout<<matrix[][].times[y]<<endl;
for(int i=;i<=n;)
for(int j=;j<=n;)
{
if(j==n&&i==n)return ;
else if(j==n)
{for(int t=i;t<n;t++)
cout<<"D";return ;
}
else if(i==n)
{for(int t=j;t<n;t++)
cout<<"R";return ;
}
if(matrix[i+][j].times[y]<=matrix[i][j+].times[y])
{
cout<<"D";
i++;
}
else
{cout<<"R";j++;}
}
cout<<endl;
}
int main()
{
int temp;//接受输入的数
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
cin>>temp;
if(!temp)
{temp=;if(!ishavezero){ishavezero=true;zeroy=j;}}
matrix[i][j]=node(get_num(temp,),get_num(temp,));
}
memset(isfind,,sizeof(isfind));//out();
dp();
memset(isfind,,sizeof(isfind));
dp();//out();
putout();
return ;
}
2017-05-12 13:21:50