The least round way 思维+DP

题目大意

给定一个 n × n n \times n n×n的矩阵，要求找到一条路径，使得路径上的矩阵元素乘积中包含的 0 0 0的数量最少。

思路

考虑 D P DP DP求解。

要使乘积中的 0 0 0最少，首先考虑如何产生 0 0 0，显然是包含有因子 2 2 2和 5 5 5的元素，末尾 0 0 0的个数取决于因子中 2 2 2和 5 5 5的个数较少的值。

那么我们只需要预处理除每个元素因子 2 2 2的个数和因子 5 5 5的个数，然后统计路径上可得到的最少因子 2 2 2和最少因子 5 5 5的个数，统计的时候，同时对路径进行标记。然后取最小值即可。

额外需要注意路径上如果有 0 0 0存在的话，需要单独处理 0 0 0。一个比较巧妙地处理方式将 0 0 0直接修改为 10 10 10，这样就不会妨碍处理了。对于有 0 0 0的情况，路径的处理也更简单一些；如果没有 0 0 0的话，则递归输出记录的路径即可。

Accepted Code

#include 
using namespace std;

const int N = 1e3 + 10;
int a[N][N][2], dp[N][N][2], path[N][N][2];

void dfs(int x,int y,int k){
	if(x == 1 && y == 1) return;
	if(path[x][y][k]) dfs(x, y - 1, k), putchar('R');
	else dfs(x - 1, y, k), putchar('D');
}

inline void solve(){
    int n = 0, flag = 0; cin >> n;
    for(int i = 1; i  num;
            if(!num) num = 10, flag = i;
            while(!(num % 2)) num >>= 1, a[i][j][0]++;
            while(!(num % 5)) num /= 5, a[i][j][1]++;
        }
    memset(dp, 0x3f, sizeof dp);
    dp[1][1][0] = a[1][1][0], dp[1][1][1] = a[1][1][1];
    
    for(int i = 1; i