题意:n * n的数字矩阵,只能向下走和向右走,要求走的数字的积的后面的0最少,求最少的0和路径之一
题解:0 的情况2 种 2 * 5 和乘以 0,记录每个数字分解的2 和 5 的数量,从左上角到右下角使用dp跑出来分别最少的2 和 5,2 和 5个数中少的那个就是答案,如果矩阵中有0就看跑出来的答案是否大于1即可,用g[][][]数组记录路径,dfs输出路径
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-4 #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int MAXN = 1e3 + 5; const int mod = 998244353; int f[MAXN][MAXN][2]; int g[MAXN][MAXN][2]; void dfs(int x,int y,int k) { if(x == 1 && y == 1) return; if(g[x][y][k]) { dfs(x - 1,y,k); putchar('D'); } else { dfs(x, y - 1,k); putchar('R'); } } int main() { int n,x = 0,k; scanf("%d",&n); memset(f,0,sizeof f); for(int i = 2; i <= n; i++) for(int id = 0; id < 2; id++) f[0][i][id] = f[i][0][id] = INF; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d",&k); if (k == 0) { x = i; } else { while (k % 2 == 0) { f[i][j][0]++; k /= 2; } while (k % 5 == 0) { f[i][j][1]++; k /= 5; } } for (int id = 0; id < 2; id++) { if (f[i - 1][j][id] < f[i][j - 1][id]) { g[i][j][id] = 1; //往下走 f[i][j][id] += f[i - 1][j][id]; } else { g[i][j][id] = 0; //往右走 f[i][j][id] += f[i][j - 1][id]; } } // debug(f[i][j][0]); // debug(f[i][j][1]); // debug(g[i][j][0]); // debug(g[i][j][1]); } } if(f[n][n][1] < f[n][n][0]) k = 1; else k = 0; if(x && f[n][n][1] > 1) { printf("1\n"); for(int i = 2; i <= x; i++) putchar('D'); for(int i = 2; i <= n; i++) putchar('R'); for(int i = x + 1; i <= n; i++) putchar('D'); } else { // debug(k); printf("%d\n",f[n][n][k]); dfs(n,n,k); } return 0; }