Codeforces_The least round way
2 seconds
64 megabytes
standard input
standard output
There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that
- starts in the upper left cell of the matrix;
- each following cell is to the right or down from the current cell;
- the way ends in the bottom right cell.
Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.
The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.
3
1 2 3
4 5 6
7 8 9
0
DDRR
题意：从左上到右下，选择一条路，使得路上每个格子中的数相乘末尾的0最少。
思路：一般情况下，只有2和5的组合才会在末尾形成0。之前一直想在dp过程中同时推2和5，然后就wa了，其实分别推2和5并记录两个路径就行，因为一般情况下，末尾0等于min(dp2[n][n],dp5[n][n])，但是还有特殊情况，就是路径中遇到0，经过0的路径最终只有一个0，但还有可能一个0都没有，要讨论全面。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
#define N 1005
#define INF 1000000
int num2[N][N],num5[N][N];
int dp2[N][N],dp5[N][N];
char dir2[N][N],dir5[N][N]; int getNum(int num,int a)
{
if(num==)
return ;
int cnt=;
while(num%a==)
{
cnt++;
num/=a;
}
return cnt;
} void dfs(char dir[][N], int x,int y)
{
if(x==&&y==)
return;
if(dir[x][y]=='R')
dfs(dir,x,y-);
else if(dir[x][y]=='D')
dfs(dir,x-,y);
printf("%c",dir[x][y]);
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int z_flag=,z_x,z_y;
memset(num2,,sizeof(num2));
memset(num5,,sizeof(num5));
memset(dp2,,sizeof(dp2));
memset(dp5,,sizeof(dp5));
//memset(dp,0,sizeof(dp));
/*for(int i=0; i<=n; i++)
{
dp2[0][i]=dp2[i][0]=INF;
dp5[0][i]=dp5[i][0]=INF;
}
dp2[0][1]=dp2[1][0]=0;
dp5[0][1]=dp5[1][0]=0;*/
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
int num;
scanf("%d",&num);
if(num)
{
num2[i][j]=getNum(num,);
num5[i][j]=getNum(num,);
}
else
{
z_flag=;
z_x=i;
z_y=j;
}
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
if(i==&&j==)
{
dir2[i][j]=' ';
dp2[i][j]=num2[i][j];
}
else if(i==)
{
dir2[i][j]='R';
dp2[i][j]=dp2[i][j-]+num2[i][j];
}
else if(j==)
{
dir2[i][j]='D';
dp2[i][j]=dp2[i-][j]+num2[i][j];
}
else
{
if(dp2[i-][j]<dp2[i][j-])
{
dir2[i][j]='D';
dp2[i][j]=dp2[i-][j]+num2[i][j];
}
else
{
dir2[i][j]='R';
dp2[i][j]=dp2[i][j-]+num2[i][j];
}
}
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
if(i==&&j==)
{
dir5[i][j]=' ';
dp5[i][j]=num5[i][j];
}
else if(i==)
{
dir5[i][j]='R';
dp5[i][j]=dp5[i][j-]+num5[i][j];
}
else if(j==)
{
dir5[i][j]='D';
dp5[i][j]=dp5[i-][j]+num5[i][j];
}
else
{
if(dp5[i-][j]<dp5[i][j-])
{
dir5[i][j]='D';
dp5[i][j]=dp5[i-][j]+num5[i][j];
}
else
{
dir5[i][j]='R';
dp5[i][j]=dp5[i][j-]+num5[i][j];
}
}
}
if(z_flag)
{
if(dp2[n][n]==)
{
printf("0\n");
dfs(dir2,n,n);
printf("\n");
}
else if(dp5[n][n]==)
{
printf("0\n");
dfs(dir5,n,n);
printf("\n");
}
else
{
printf("1\n");
for(int i=;i<z_x;i++)
printf("D");
for(int i=;i<n;i++)
printf("R");
for(int i=z_x;i<n;i++)
printf("D");
printf("\n");
}
}
else
{
if(dp2[n][n]<dp5[n][n])
{
printf("%d\n",dp2[n][n]);
dfs(dir2,n,n);
printf("\n");
}
else
{
printf("%d\n",dp5[n][n]);
dfs(dir5,n,n);
printf("\n");
}
}
}
return ;
}
最新文章
- MSSQLSERVER执行计划详解
- vmware centos nat模式下连不上网络解决办法
- JQuery data方法的使用-遁地龙卷风
- C语言文件操作
- eclipse4.4 tomcat jrebel使用
- leetcode@ [289] Game of Life (Array)
- poj 3422 (费用流)
- 守护进程VS守护线程
- TDD入门demo
- 市面上有没有靠谱的PM2.5检测仪？如何自己动手制作PM2.5检测仪
- [USACO Jan09] 安全路径
- C语言程序设计第六次作业--循环结构2
- Python入门—文件读写
- webpack4.0各个击破（8）—— tapable篇
- JavaScript实现循环链表
- Crazy Circuits HDU - 3157（有源汇有上下界最小流）
- [python] 基础工具介绍好文推荐
- 牛客国庆集训派对Day4 J-寻找复读机
- <转载> MySQL 性能优化的最佳20多条经验分享 http://www.jb51.net/article/24392.htm
- 用VS2010打开VS2012项目