【Codeforces Beta Round 2B】【贪心 DP】The least round way 从（1，1）走到（n，n）乘积尾数0尽可能少

本文主要是介绍【Codeforces Beta Round 2B】【贪心 DP】The least round way 从（1，1）走到（n，n）乘积尾数0尽可能少，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

Input

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 10⁹).

Output

In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

Sample test(s) 
input 
3
1 2 3
4 5 6
7 8 9
output 
0
DDRR

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
const int N=1000+5,M=0,Z=1e9+7,ms63=1061109567;
int n,v;
int f2[N][N];
int f5[N][N];
void go(int f[N][N],int y,int x)
{if(y==1&&x==1)return;if(f[y-1][x]<f[y][x-1]){go(f,y-1,x);printf("D");}else{go(f,y,x-1);printf("R");}
}
void walk(int y,int x,int edy,int edx)
{while(y!=edy){printf("D");++y;}while(x!=edx){printf("R");++x;}
}
int main()
{while(~scanf("%d",&n)){MS(f2,1);MS(f5,1);f2[0][1]=f5[0][1]=0;bool zero=0;int y,x;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){int v,v2,v5;scanf("%d",&v);if(v==0){zero=1;y=i,x=j;continue;}for(v2=0;v%2==0;v/=2)++v2;for(v5=0;v%5==0;v/=5)++v5;f2[i][j]=min(f2[i-1][j],f2[i][j-1])+v2;f5[i][j]=min(f5[i-1][j],f5[i][j-1])+v5;}}int ans=min(f2[n][n],f5[n][n]);if(zero)gmin(ans,1);printf("%d\n",ans);if(ans==f2[n][n])go(f2,n,n);else if(ans==f5[n][n])go(f5,n,n);else{walk(1,1,y,x);walk(y,x,n,n);}puts("");}return 0;
}
/*
【trick&&吐槽】
如果题目难，我就简化问题【题意】
给你一个n*n的数值矩阵a[][]，
让你从左上角走到右下角，并把所有数值乘起来，使得最后尾巴上0的个数尽可能少。
n的范围是[2,1000]，a[][]的范围是[0,1e9]【类型】
DP【分析】
一定要好好贯彻落实——"如果题目难，我就简化问题"的重要思想。这道题就是个典型。
我一开始想的是，用f[i][j][k]表示走到[i][j]位置，k个2的条件下最少的5的数量。
然而，显然这个DP的复杂度爆表。然而我们隐隐约约有一种想法，显然，最后0的个数，是由min（2，5）决定的。
于是，我们不妨不去考虑去做两个DP
分别是追求最少数量的2，和最少数量的5，这样，min（min2，min5）肯定是我们的备选答案之一。
然而还有一种情况需要考虑，就是如果a[][]中有0，那么1是备选答案之一。呀，这道题就这样做完啦！
我们按照这个答案记录路径并暑促答案就可以AC啦！【时间复杂度&&优化】
O(n^2)*/

这篇关于【Codeforces Beta Round 2B】【贪心 DP】The least round way 从（1，1）走到（n，n）乘积尾数0尽可能少的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！