这个2B题还好~~
题目大意：
给出一个矩阵。从左上走到右下，仅仅能往右或下走。路径中每一个格子有一个数。这些数相乘得出一个数。
求这个数末尾零最少的一条路径。
解题思路：
找出一条路径。乘积得数中素因子2的个数最少，再找出一个素因子5最少， 比較两个输出最小的。
有意外情况就是有数为零。这样的情况把零当成10跑一遍，假设素因子最少为0。输出路径，假设不是，输出经过零的路径。
以下是代码：
#include <set> #include <map> #include <queue> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <cctype> #include <algorithm> #define eps 1e-10 #define pi acos(-1.0) #define inf 107374182 #define inf64 1152921504606846976 #define lc l,m,tr<<1 #define rc m + 1,r,tr<<1|1 #define zero(a) fabs(a)<eps #define iabs(x) ((x) > 0 ?(x) : -(x)) #define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (min(SIZE,sizeof(A)))) #define clearall(A, X) memset(A, X, sizeof(A)) #define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE)) #define memcopyall(A, X) memcpy(A , X ,sizeof(X)) #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ?
(x) : (y) ) using namespace std; int dp[1005][1005][2]; int cnt[1005][1005][2]; int pre[1005][1005][2]; void output(int x,int y,int num) { if(x==0&&y==0)return ; if(pre[x][y][num]==0) { output(x,y-1,num); printf("R"); } else { output(x-1,y,num); printf("D"); } } int main() { int input,n,x=-1,y=-1; scanf("%d",&n); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { scanf("%d",&input); if(input==0) { cnt[i][j][0]=1; cnt[i][j][1]=1; x=i; y=j; continue; } cnt[i][j][0]=0; while(input%2==0) { cnt[i][j][0]++; input/=2; } cnt[i][j][1]=0; while(input%5==0) { cnt[i][j][1]++; input/=5; } } } clearall(pre,-1); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(i==0) { if(j==0) { dp[0][0][0]=cnt[0][0][0]; dp[0][0][1]=cnt[0][0][1]; } else { dp[0][j][0]=cnt[0][j][0]+dp[0][j-1][0]; dp[0][j][1]=cnt[0][j][1]+dp[0][j-1][1]; pre[0][j][0]=0; pre[0][j][1]=0; } } else if(j==0) { dp[i][0][0]=dp[i-1][0][0]+cnt[i][0][0]; dp[i][0][1]=dp[i-1][0][1]+cnt[i][0][1]; pre[i][0][0]=1; pre[i][0][1]=1; } else { if(dp[i][j-1][0]>dp[i-1][j][0]) { dp[i][j][0]=dp[i-1][j][0]+cnt[i][j][0]; pre[i][j][0]=1; } else { dp[i][j][0]=dp[i][j-1][0]+cnt[i][j][0]; pre[i][j][0]=0; } if(dp[i][j-1][1]>dp[i-1][j][1]) { dp[i][j][1]=dp[i-1][j][1]+cnt[i][j][1]; pre[i][j][1]=1; } else { dp[i][j][1]=dp[i][j-1][1]+cnt[i][j][1]; pre[i][j][1]=0; } } } } if(x!=-1) { if(min(dp[n-1][n-1][0],dp[n-1][n-1][1])==0) { printf("0 "); if(dp[n-1][n-1][0]==0)output(n-1,n-1,0); else output(n-1,n-1,1); } else { printf("1 "); for(int i=0;i<n-1;i++) { if(i==x) { for(int j=0;j<n-1;j++) { printf("R"); } } printf("D"); } } } else { printf("%d ",min(dp[n-1][n-1][0],dp[n-1][n-1][1])); if(dp[n-1][n-1][0]<dp[n-1][n-1][1]) { output(n-1,n-1,0); } else output(n-1,n-1,1); } return 0; }