Description
有一个n*n的正整数矩阵，要你求一条从第一行第一列的格子到第n行第n列的路，使得你走过的格子里面的数乘起来的值末尾的零的个数最小。输出最小个数。
Input
第一行包含1个数n。接下来n行每行n个数字。
Output
一个数字表示末尾零最小个数。
Sample Input31 2 34 5 67 8 9Sample Output0由于都是正数，对这个来说只需统计最少的2或5即可。相对简单。#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF=0x3f3f3f3f;const int maxn=1010;int dp[maxn][maxn][2];int path[maxn][maxn][2];int mp[maxn][maxn][2];int n;void print(int i,int j){if(i==1&&j==1)return ;print(path[i][j][0],path[i][j][1]);if(i-path[i][j][0]==1&&j==path[i][j][1]) printf("%c",'D');else printf("%c",'R');}int main(){int x,cnt1,cnt2,temp;while(~scanf("%d",&n)){REPF(i,1,n){REPF(j,1,n){scanf("%d",&x);cnt1=cnt2=0;temp=x;while(temp%2==0){temp/=2;cnt1++;}while(x%5==0){x/=5;cnt2++;}mp[i][j][0]=cnt1;mp[i][j][1]=cnt2;}}CLEAR(dp,INF);dp[1][1][0]=mp[1][1][0];dp[1][1][1]=mp[1][1][1];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=0;k<2;k++)//0:2 1:5{if(i>1&&dp[i][j][k]>dp[i-1][j][k]+mp[i][j][k]){dp[i][j][k]=dp[i-1][j][k]+mp[i][j][k];path[i][j][0]=i-1;path[i][j][1]=j;}if(j>1&&dp[i][j][k]>dp[i][j-1][k]+mp[i][j][k]){dp[i][j][k]=dp[i][j-1][k]+mp[i][j][k];path[i][j][0]=i;path[i][j][1]=j-1;}}}}printf("%d\n",min(dp[n][n][0],dp[n][n][1]));//print(n,n);//puts("");}return 0;}/*再看Codeforces 2B:
Description
There is a square matrixn×n, consisting of non-negative integer numbers. You should find such a way on it that
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 numbern(2≤n≤1000),nis the size of the matrix. Then follownlines containing the matrix elements (non-negative integer numbers not exceeding109).
Output
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.
Sample Input
Input
31 2 34 5 67 8 9
Output
0DDRR
Source
不仅要输出路径，，而且矩阵中还带了0，这就是麻烦的地方；
题解：对于要输出的路径，记录前面的一个状态即可，对于0的处理，如果到终点的2或
5的个数大于等于1了，而矩阵中含0，这时候就是直接答案就是1个0，路径只需找到任意
一个0所在的行列输出即可。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF=0x3f3f3f3f;const int maxn=1010;int dp[maxn][maxn][2];int path1[maxn][maxn][2];int path2[maxn][maxn][2];int mp[maxn][maxn][2];int n;void print1(int i,int j){if(i==1&&j==1)return ;print1(path1[i][j][0],path1[i][j][1]);if(i-path1[i][j][0]==1&&j==path1[i][j][1]) printf("%c",'D');else printf("%c",'R');}void print2(int i,int j){if(i==1&&j==1)return ;print2(path2[i][j][0],path2[i][j][1]);if(i-path2[i][j][0]==1&&j==path2[i][j][1]) printf("%c",'D');else printf("%c",'R');}int main(){int x,cnt1,cnt2,temp,ans;int sx,sy;while(~scanf("%d",&n)){int flag=1;CLEAR(mp,0);REPF(i,1,n){REPF(j,1,n){scanf("%d",&x);cnt1=cnt2=0;temp=x;if(x==0){mp[i][j][0]=mp[i][j][1]=1;sx=i;sy=j;flag=0;continue;}while(temp%2==0){temp/=2;cnt1++;}while(x%5==0){x/=5;cnt2++;}mp[i][j][0]=cnt1;mp[i][j][1]=cnt2;}}CLEAR(dp,INF);dp[1][1][0]=mp[1][1][0];dp[1][1][1]=mp[1][1][1];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=0;k<2;k++)//0:2 1:5{if(i>1&&dp[i][j][k]>dp[i-1][j][k]+mp[i][j][k]){dp[i][j][k]=dp[i-1][j][k]+mp[i][j][k];if(!k){path1[i][j][0]=i-1;path1[i][j][1]=j;}else{path2[i][j][0]=i-1;path2[i][j][1]=j;}}if(j>1&&dp[i][j][k]>dp[i][j-1][k]+mp[i][j][k]){dp[i][j][k]=dp[i][j-1][k]+mp[i][j][k];if(!k){path1[i][j][0]=i;path1[i][j][1]=j-1;}else{path2[i][j][0]=i;path2[i][j][1]=j-1;}}}}}ans=min(dp[n][n][0],dp[n][n][1]);if(ans>=1&&!flag){printf("%d\n",1);for(int i=0;i<sx-1;i++)printf("%c",'D');for(int i=0;i<sy-1;i++)printf("%c",'R');for(int i=sx;i<n;i++)printf("%c",'D');for(int i=sy;i<n;i++)printf("%c",'R');puts("");continue;}printf("%d\n",ans);if(ans==dp[n][n][0]) print1(n,n);else print2(n,n);puts("");}return 0;}/*32 2 22 2 25 5 5*/
你看报表时，梅里雪山的金丝猴刚好爬上树尖。
