Topic link

Train of thought

The trailing zero can only come from the product of 2 and 5, except in cases where the final result is 0. Dynamic programming can be used to figure out the number of times to the terminal number including 2 and 5 as factors, and the minimum value of the two is the number of 0 at the end. If you have a zero in the graph, if you go through this point you’re going to end up with only one zero, so if you do it separately, you don’t go through zero if you don’t go through zero, otherwise you go straight to zero. Look at the web solutions, you can do a reverse search when printing the answers to ensure the correct order of output, and a small detail of initialization.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
using namespace std;
const int N=1E3+10,INF=0x3f3f3f3f;
int n,dir,zero;
int f[N][N][2];
void dfs(int x,int y)
{
	if(x==1 && y==1)
		return;
	if(f[x- 1][y][dir]>f[x][y- 1][dir])
	{
		dfs(x,y- 1);
		putchar('R');
	}
	else
	{
		dfs(x- 1,y);
		putchar('D'); }}int main(a)
{
	cin>>n;
	rep(i,2,n)
		f[i][0] [0]=f[i][0] [1]=f[0][i][0]=f[0][i][1]=INF;
	rep(i,1,n)
	{
		rep(j,1,n)
		{
			int k;
			scanf("%d",&k);
			if(k==0)
			{
				zero=i;
				continue;
			}
			while(k%2= =0)
			{
				++f[i][j][0];
				k>>=1;
			}
			while(k%5= =0)
			{
				++f[i][j][1];
				k/=5;
			}
			rep(p,0.1)
			{
				if(f[i- 1][j][p]<f[i][j- 1][p])
					f[i][j][p]+=f[i- 1][j][p];
				else
					f[i][j][p]+=f[i][j- 1][p];
			}
		}
	}
	dir=f[n][n][0]>f[n][n][1];
	if(min(f[n][n][0],f[n][n][1) >1 && zero)
	{
		cout<<1<<endl;
		rep(i,2,zero)
			putchar('D');
		rep(i,2,n)
			putchar('R');
		rep(i,zero+1,n)
			putchar('D');
		return 0;
	}
	cout<<min(f[n][n][0],f[n][n][1])<<endl;
	dfs(n,n);
}
Copy the code

Refer to the blog